Hardness and approximation results for packing Steiner trees

DOI10.1007/S00453-005-1188-4zbMath1117.68054OpenAlexW2154295079MaRDI QIDQ2369873

Mohammad R. Salavatipour, Joseph Cheriyan

Publication date: 21 June 2007

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-005-1188-4

zbMATH Keywords

packing edge-disjoint Steiner trees of undirected graphspacking Steiner-node-disjoint Steiner trees of undirected graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (8)

The data transfer problem in a system of systems ⋮ Minimally strong subgraph \((k,\ell ) \)-arc-connected digraphs ⋮ Packing Steiner trees on four terminals ⋮ Directed Steiner tree packing and directed tree connectivity ⋮ Packing strong subgraph in digraphs ⋮ Unnamed Item ⋮ Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs ⋮ Extremal results for directed tree connectivity

Cites Work

• Unnamed Item
• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• The directed subgraph homeomorphism problem
• The Steiner tree packing problem in VLSI design
• Edge-disjoint trees containing some given vertices in a graph
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• Approximating disjoint-path problems using packing integer programs
• Packing Steiner trees with identical terminal sets
• Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
• Randomized metarounding
• Approximating theDomatic Number
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Approximation Algorithms for Directed Steiner Problems
• Algorithms – ESA 2004
• Fundamentals of Computation Theory
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

This page was built for publication: Hardness and approximation results for packing Steiner trees