The complexity of the locally connected spanning tree problem

DOI10.1016/S0166-218X(02)00417-1zbMath1022.05079MaRDI QIDQ1408813

Leizhen Cai

Publication date: 25 September 2003

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

zbMATH Keywords

split graphplanar graph2-treedirected path graphlocally connected spanning treealgorithm and complexity

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs ⋮ 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 ⋮ Hamiltonian properties of locally connected graphs with bounded vertex degree ⋮ 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the SPANNING \(k\)-TREE problem
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• On spanning 2-trees in a graph
• Steiner trees, partial 2–trees, and minimum IFI networks
• Fast Algorithms for Finding Nearest Common Ancestors
• Networks immune to isolated failures
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Graph Classes: A Survey

This page was built for publication: The complexity of the locally connected spanning tree problem