An approximate max-Steiner-tree-packing min-Steiner-cut theorem

DOI10.1007/S00493-007-0044-3MaRDI QIDQ925137zbMATHOpenAlexFDO

Authors Chi Lau Lap

Publication date 29 May 2008

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-007-0044-3

zbMATH Keywords

approximation algorithm treesSteiner tree packing problem

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 2079349
• Packing Steiner Forests
• Packing Steiner trees
• Packing the Steiner trees of a graph
• Algorithms – ESA 2004

Cited in

(20)

• Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs
• Packing Steiner trees
• Approximate integer decompositions for undirected network design problems
• Packing strong subgraph in digraphs
• Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
• Steiner tree packing number and tree connectivity
• 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
• On extremal graphs with at most \(\ell\) internally disjoint Steiner trees connecting any \(n-1\) vertices
• Packing Steiner trees on four terminals
• Hamilton cycles in line graphs of 3-hypergraphs
• Packing Steiner Forests
• Packing of Steiner trees and \(S\)-connectors in graphs
• Edge disjoint Steiner trees in graphs without large bridges
• scientific article; zbMATH DE number 2079349 (Why is no real title available?)
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
• Spanning trees: A survey

This page was built for publication: An approximate max-Steiner-tree-packing min-Steiner-cut theorem

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