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

DOI10.1007/s00493-007-0044-3zbMath1136.05011OpenAlexW2097945626MaRDI QIDQ925137

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (14)

Packing Steiner trees ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Hamilton cycles in line graphs of 3-hypergraphs ⋮ Packing Steiner trees on four terminals ⋮ 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 strong subgraph in digraphs ⋮ The \(\kappa_k\)-connectivity of line graphs ⋮ Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs ⋮ Edge-disjoint Steiner trees and connectors in graphs ⋮ Spanning trees: A survey ⋮ Steiner tree packing number and tree connectivity ⋮ Packing of Steiner trees and \(S\)-connectors in graphs ⋮ Edge disjoint Steiner trees in graphs without large bridges

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