On the SPANNING k-TREE problem

DOI10.1016/0166-218X(93)90228-GMaRDI QIDQ686254zbMATH OpenOpenAlexFDO

Authors Leizhen Cai, Frédéric Maffray

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

NP-completespanning tree\(k\)-tree

Mathematics Subject Classification ID

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

Recommendations

• The \((K, k)\)-capacitated spanning tree problem
• The (K,k)-Capacitated Spanning Tree Problem
• On tree-\(t\)-spanners in graphs
• On tree-\(t\)-spanners in graphs
• Spanning \(k\)-trees of \(n\)-connected graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Complexities of some interesting problems on spanning trees
• scientific article; zbMATH DE number 861414
• Approximating the Spanning k-Tree Forest Problem
• Approximating the spanning \(k\)-tree forest problem

Cites work

• scientific article; zbMATH DE number 3172312 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3869366 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Algorithmic Aspects of Vertex Elimination on Graphs
• Complexity of Finding Embeddings in a k-Tree
• Networks immune to isolated failures
• On rigid circuit graphs
• On simple characterizations of k-trees
• Planar Formulae and Their Uses
• Properties and characterizations of k ‐trees
• Split Graphs Having Dilworth Number Two
• Steiner trees, partial 2–trees, and minimum IFI networks

Cited in

(24)

• The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
• scientific article; zbMATH DE number 804636 (Why is no real title available?)
• A \((1/2+1/60)\)-approximation algorithm for maximum weight series-parallel subgraph
• The complexity of the locally connected spanning tree problem
• On the complexity of some subgraph problems
• scientific article; zbMATH DE number 1330076 (Why is no real title available?)
• Heuristics for the network design problem with connectivity requirements
• The three-in-a-tree problem
• scientific article; zbMATH DE number 7526265 (Why is no real title available?)
• On spanning 2-trees in a graph
• On a spanning \(K\)-tree containing specified vertices in a graph
• Plane Triangulations Without Spanning 2-Trees
• On the spanning tree polyhedron
• On finding most uniform spanning trees
• The (K,k)-Capacitated Spanning Tree Problem
• scientific article; zbMATH DE number 3855138 (Why is no real title available?)
• Maximum series-parallel subgraph
• The 2-hop spanning tree problem
• NP-completeness and degree restricted spanning trees
• On the Red/Blue Spanning Tree Problem
• On a spanning \(k\)-tree in which specified vertices have degree less than \(k\)
• Complexity of some graph-based bounds on the probability of a union of events
• On the \(K\) shortest path trees problem
• Optimal decomposition and recombination of isostatic geometric constraint systems for designing layered materials

This page was built for publication: On the SPANNING \(k\)-TREE problem

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