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

DOI10.1016/j.disc.2006.06.026zbMath1119.05102OpenAlexW2037551081MaRDI 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

algorithminterval graphstrongly chordal graphcircular-arc graphdirected path graphlocally connected spanning treeproper circular-arc graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs ⋮ A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs ⋮ Spanning trees: A survey ⋮ A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs

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

This page was built for publication: Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs