pith. sign in

arxiv: cs/0409013 · v1 · submitted 2004-09-08 · 💻 cs.DS · cs.DM

Locally connected spanning trees on graphs

classification 💻 cs.DS cs.DM
keywords connectedspanninggraphslocallytreetreesalgorithmschordal
0
0 comments X
read the original abstract

A locally connected spanning tree of a graph $G$ is a spanning tree $T$ of $G$ such that the set of all neighbors of $v$ in $T$ induces a connected subgraph of $G$ for every $v\in V(G)$. The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.