Hardness and approximation results for packing Steiner trees

DOI10.1007/S00453-005-1188-4MaRDI QIDQ2369873zbMATH OpenOpenAlexFDO

Authors Mohammad 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

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

Recommendations

• Algorithms – ESA 2004
• Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
• Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs
• Packing the Steiner trees of a graph
• scientific article; zbMATH DE number 108281
• scientific article; zbMATH DE number 2089220
• Packing Steiner trees: Further facets
• Packing Steiner trees: A cutting plane algorithm and computational results
• Packing Steiner Forests
• Steiner tree packing revisited

Cites work

• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Algorithms – ESA 2004
• Approximating disjoint-path problems using packing integer programs
• Approximating theDomatic Number
• Approximation Algorithms for Directed Steiner Problems
• Approximation algorithms for disjoint paths and related routing and packing problems
• Edge-disjoint trees containing some given vertices in a graph
• scientific article; zbMATH DE number 508829 (Why is no real title available?)
• scientific article; zbMATH DE number 1522943 (Why is no real title available?)
• Inapproximability results for bounded variants of optimization problems.
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• On the complexity of approximating \(k\)-dimensional matching
• Packing Steiner trees with identical terminal sets
• Randomized metarounding
• The directed subgraph homeomorphism problem
• The Steiner tree packing problem in VLSI design

Cited in

(13)

• Packing Steiner trees: A cutting plane algorithm and computational results
• Extremal results for directed tree connectivity
• Minimally strong subgraph \((k,\ell ) \)-arc-connected digraphs
• Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
• Packing strong subgraph in digraphs
• The data transfer problem in a system of systems
• The cavity approach for Steiner trees packing problems
• scientific article; zbMATH DE number 108281 (Why is no real title available?)
• Greedy algorithms for online survivable network design
• Algorithms – ESA 2004
• Packing Steiner trees on four terminals
• Directed Steiner tree packing and directed tree connectivity
• Perfect out-forest problem and directed Steiner cycle packing problem

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

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