Hardness and approximation results for packing Steiner trees
DOI10.1007/S00453-005-1188-4zbMATH Open1117.68054OpenAlexW2154295079MaRDI QIDQ2369873FDOQ2369873
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
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
packing edge-disjoint Steiner trees of undirected graphspacking Steiner-node-disjoint Steiner trees of undirected graphs
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)
Cites Work
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- The directed subgraph homeomorphism problem
- Approximation Algorithms for Directed Steiner Problems
- Inapproximability results for bounded variants of optimization problems.
- Edge-disjoint trees containing some given vertices in a graph
- On decomposing a hypergraph into \(k\) connected sub-hypergraphs
- Approximating theDomatic Number
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- The Steiner tree packing problem in VLSI design
- Randomized metarounding
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
- Approximating disjoint-path problems using packing integer programs
- Approximation algorithms for disjoint paths and related routing and packing problems
- On the complexity of approximating \(k\)-dimensional matching
- Title not available (Why is that?)
- Title not available (Why is that?)
- Algorithms – ESA 2004
- Packing Steiner trees with identical terminal sets
Cited In (12)
- Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
- Directed Steiner tree packing and directed tree connectivity
- Extremal results for directed tree connectivity
- The cavity approach for Steiner trees packing problems
- Greedy algorithms for online survivable network design
- Packing Steiner trees on four terminals
- The data transfer problem in a system of systems
- Minimally strong subgraph \((k,\ell ) \)-arc-connected digraphs
- Title not available (Why is that?)
- Packing strong subgraph in digraphs
- Algorithms – ESA 2004
- Packing Steiner trees: A cutting plane algorithm and computational results
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)
