Name
Title | ||
|---|---|---|
A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs |
Abstract | ||
|---|---|---|
A locally connected spanning tree (LCST) T of a graph G is a spanning tree of G such that, for each node, its neighborhood in T induces a connected subgraph in G. The problem of determining whether a graph contains an LCST or not has been proved to be NP-complete, even if the graph is planar or chordal. The main result of this paper is a simple linear time algorithm that, given a maximal planar chordal graph, determines in linear time whether it contains an LCST or not, and produces one if it exists. We give an analogous result for the case when the input graph is a maximal outerplanar graph. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.tcs.2018.02.025 | Theoretical Computer Science |
Keywords | Field | DocType |
Locally connected spanning tree,Partial k trees,SC k-trees,2-Trees,Chordal graphs,Planar graphs | Graph,Discrete mathematics,Outerplanar graph,Combinatorics,Chordal graph,Algorithm,Vertex connectivity,Planar,Spanning tree,Time complexity,Mathematics | Journal |
Volume | ISSN | Citations |
764 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| T. Calamoneri | 1 | 27 | 2.87 |
| Matteo Dell'Orefice | 2 | 0 | 0.68 |
| Angelo Monti | 3 | 671 | 46.93 |