Packing Steiner trees

DOI10.1016/J.JCTB.2016.02.002MaRDI QIDQ273179zbMATHOpenAlexFDO

Authors Matt DeVos, Jessica McDonald, Irene Pivotto

Publication date 21 April 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.7621

zbMATH Keywords

packingSteiner trees

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $T$ be a distinguished subset of vertices in a graph $G$. A $T$-emph{Steiner tree} is a subgraph of $G$ that is a tree and that spans $T$. Kriesell conjectured that $G$ contains $k$ pairwise edge-disjoint $T$-Steiner trees provided that every edge-cut of $G$ that separates $T$ has size $ge2k$. When $T=V(G)$ a $T$-Steiner tree is a spanning tree and the conjecture is a consequence of a classic theorem due to Nash-Williams and Tutte. Lau proved that Kriesell's conjecture holds when $2k$ is replaced by $24k$, and recently West and Wu have lowered this value to $6.5k$. Our main result makes a further improvement to $5k+4$.

Recommendations

• Packing the Steiner trees of a graph
• Packing of Steiner trees and \(S\)-connectors in graphs
• Steiner tree packing number and tree connectivity
• Edge-disjoint Steiner trees and connectors in graphs
• scientific article; zbMATH DE number 2079349

Cites work

• scientific article; zbMATH DE number 3512137 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A Reduction Method for Edge-Connectivity in Graphs
• A THEOREM ON INDEPENDENCE RELATIONS
• An approximate max-Steiner-tree-packing min-Steiner-cut theorem
• Degree Bounded Matroids and Submodular Flows
• Edge-Disjoint Spanning Trees of Finite Graphs
• Edge-disjoint trees containing some given vertices in a graph
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• On the Problem of Decomposing a Graph into n Connected Factors
• Packing of Steiner trees and \(S\)-connectors in graphs

Cited in

(21)

• scientific article; zbMATH DE number 108281 (Why is no real title available?)
• Bounds on the maximum number of edge-disjoint Steiner trees of a graph
• Approximate integer decompositions for undirected network design problems
• Packing strong subgraph in digraphs
• The 2-Steiner distance matrix of a tree
• Packing the Steiner trees of a graph
• Steiner tree packing number and tree connectivity
• Packing Steiner trees: A cutting plane algorithm and computational results
• On the Edge-Erdős–Pósa Property of Ladders
• The \(\kappa_k\)-connectivity of line graphs
• Edge-disjoint Steiner trees and connectors in graphs
• Directed Steiner tree packing and directed tree connectivity
• Globally balancing spanning trees
• Packing Steiner trees on four terminals
• Hamilton cycles in line graphs of 3-hypergraphs
• Packing element-disjoint steiner trees
• Packing Steiner Forests
• Packing of Steiner trees and \(S\)-connectors in graphs
• Edge disjoint Steiner trees in graphs without large bridges
• The Steiner tree packing problem in VLSI design
• An approximate max-Steiner-tree-packing min-Steiner-cut theorem

This page was built for publication: Packing Steiner trees

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