Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

DOI10.1016/j.disc.2006.06.026zbMath1119.05102MaRDI QIDQ864162

Gen-Huey Chen, Ching-Chi Lin, Gerard Jennhwa Chang

Publication date: 13 February 2007

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2006.06.026

zbMATH Keywords

algorithm; interval graph; strongly chordal graph; circular-arc graph; directed path graph; locally connected spanning tree; proper circular-arc graph

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C75: Structural characterization of families of graphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Spanning trees: A survey

Cites Work

• Unnamed Item
• Characterizations of strongly chordal graphs
• On spanning 2-trees in a graph
• The complexity of the locally connected spanning tree problem
• Linear-time recognition of circular-arc graphs
• Doubly lexical ordering of dense 0--1 matrices
• Steiner trees, partial 2–trees, and minimum IFI networks
• Characterizations of totally balanced matrices
• Totally-Balanced and Greedy Matrices
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Doubly Lexical Orderings of Matrices
• Three Partition Refinement Algorithms
• Networks immune to isolated failures
• Networks immune to isolated line failures