Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
From MaRDI portal
(Redirected from Publication:2429344)
approximation algorithmsNP-hardpackingplanar graphshardness of approximationSteiner treesedge connectivityelement connectivitypartition connectivity
Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Recommendations
- Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs
- Packing element-disjoint steiner trees
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Approximation algorithms for packing element-disjoint Steiner trees on bounded terminal nodes
- A graph reduction step preserving element-connectivity and packing Steiner trees and forests
Cites work
- scientific article; zbMATH DE number 4191148 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 508829 (Why is no real title available?)
- scientific article; zbMATH DE number 508831 (Why is no real title available?)
- scientific article; zbMATH DE number 1146232 (Why is no real title available?)
- scientific article; zbMATH DE number 2079349 (Why is no real title available?)
- A Graph Reduction Step Preserving Element-Connectivity and Applications
- An approximate max-Steiner-tree-packing min-Steiner-cut theorem
- An extremal function for contractions of graphs
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Disjoint bases in a polymatroid
- Edge-Disjoint Spanning Trees of Finite Graphs
- Exact and approximate balanced data gathering in energy-constrained sensor networks
- Hardness and approximation results for packing Steiner trees
- Lower bound of the Hadwiger number of graphs by their average degree
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Minimum partition of a matroid into independent subsets
- Multiflow Feasibility: An Annotated Tableau
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
- Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
- On decomposing a hypergraph into \(k\) connected sub-hypergraphs
- On the Problem of Decomposing a Graph into n Connected Factors
- On the complexity of the disjoint paths problem
- Packing Steiner Trees: Separation Algorithms
- Packing Steiner trees with identical terminal sets
- Packing Steiner trees: A cutting plane algorithm and computational results
- Packing Steiner trees: Further facets
- Packing Steiner trees: Polyhedral investigations
- Packing of Steiner trees and \(S\)-connectors in graphs
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- The Steiner tree packing problem in VLSI design
Cited in
(15)- scientific article; zbMATH DE number 7561717 (Why is no real title available?)
- A graph reduction step preserving element-connectivity and packing Steiner trees and forests
- Packing element-disjoint steiner trees
- Approximation algorithms for solving the 1-line minimum Steiner tree of line segments problem
- An exact algorithm for the line-constrained bottleneck \(k\)-Steiner tree problem
- Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
- Approximation algorithms for packing element-disjoint Steiner trees on bounded terminal nodes
- Reliability assessment of the divide-and-swap cube in terms of generalized connectivity
- Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs
- On element-connectivity preserving graph simplification
- Algorithms – ESA 2004
- The \(\kappa_k\)-connectivity of line graphs
- \(1\)-line minimum rectilinear Steiner trees and related problems
- Hardness and approximation results for packing Steiner trees
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
This page was built for publication: Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429344)
