On the SPANNING \(k\)-TREE problem

DOI10.1016/0166-218X(93)90228-GzbMath0788.68107OpenAlexW2062226917MaRDI QIDQ686254

Frédéric Maffray, Leizhen Cai

Publication date: 30 November 1993

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

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90228-g

zbMATH Keywords

spanning tree\(k\)-treeNP-complete

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Heuristics for the network design problem with connectivity requirements ⋮ Optimal decomposition and recombination of isostatic geometric constraint systems for designing layered materials ⋮ On spanning 2-trees in a graph ⋮ Maximum series-parallel subgraph ⋮ The complexity of the locally connected spanning tree problem ⋮ Plane Triangulations Without Spanning 2-Trees ⋮ Complexity of some graph-based bounds on the probability of a union of events ⋮ On the complexity of some subgraph problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• On simple characterizations of k-trees
• Steiner trees, partial 2–trees, and minimum IFI networks
• Complexity of Finding Embeddings in a k-Tree
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Networks immune to isolated failures
• Planar Formulae and Their Uses
• Split Graphs Having Dilworth Number Two
• Algorithmic Aspects of Vertex Elimination on Graphs
• Properties and characterizations of k ‐trees
• A Characterization of Comparability Graphs and of Interval Graphs