The complexity of the locally connected spanning tree problem

DOI10.1016/S0166-218X(02)00417-1MaRDI QIDQ1408813zbMATH OpenFDO

Authors 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs
• Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
• A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs
• A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
• Complexity results for the spanning tree congestion problem

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• Fast Algorithms for Finding Nearest Common Ancestors
• Graph Classes: A Survey
• Graph theory
• Networks immune to isolated failures
• On spanning 2-trees in a graph
• On the SPANNING \(k\)-TREE problem
• Steiner trees, partial 2–trees, and minimum IFI networks
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(10)

• A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs
• Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
• Complexity of the directed spanning cactus problem
• Polynomially determining spanning connectivity of locally connected line 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
• Using local adaptations to reconfigure a spanning tree of a network
• Hamiltonian properties of locally connected graphs with bounded vertex degree
• Complexity of spanning tree problems with leaf-dependent objectives
• Spanning trees: A survey

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1408813)