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

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

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

• scientific article; zbMATH DE number 508829 (Why is no real title available?)
• scientific article; zbMATH DE number 1522943 (Why is no real title available?)
• 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
• 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 Steiner tree packing problem in VLSI design
• The directed subgraph homeomorphism problem

Cited in

(12)

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

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)