On the SPANNING k-TREE problem

DOI10.1016/0166-218X(93)90228-GzbMATH Open0788.68107OpenAlexW2062226917MaRDI QIDQ686254FDOQ686254

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

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

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)

Cites Work

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

Cited In (23)

• A \((1/2+1/60)\)-approximation algorithm for maximum weight series-parallel subgraph
• On spanning 2-trees in a graph
• Title not available (Why is that?)
• On the Red/Blue Spanning Tree Problem
• On a spanning \(k\)-tree in which specified vertices have degree less than \(k\)
• On the complexity of some subgraph problems
• Heuristics for the network design problem with connectivity requirements
• Optimal decomposition and recombination of isostatic geometric constraint systems for designing layered materials
• Title not available (Why is that?)
• On a spanning \(K\)-tree containing specified vertices in a graph
• On the \(K\) shortest path trees problem
• The three-in-a-tree problem
• On the spanning tree polyhedron
• The (K,k)-Capacitated Spanning Tree Problem
• Title not available (Why is that?)
• Complexity of some graph-based bounds on the probability of a union of events
• NP-completeness and degree restricted spanning trees
• Plane Triangulations Without Spanning 2-Trees
• The 2-hop spanning tree problem
• The complexity of the locally connected spanning tree problem
• Title not available (Why is that?)
• Maximum series-parallel subgraph
• On finding most uniform spanning trees

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)