|
|||||
|
|
Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs |
|
| Authors: | Ching-Chi Lin Gen-Huey Chen |
| Affiliation: | a Department of Computer Science and Information Engineering, National Taiwan University, Taipei 10617, Taiwan b Department of Mathematics, National Taiwan University, Taipei 10617, Taiwan |
| 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∈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. |
| Keywords: | Algorithm Circular-arc graph Directed path graph Interval graph Locally connected spanning tree Proper circular-arc graph Strongly chordal graph |
| 本文献已被 ScienceDirect 等数据库收录！ | |