Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs

DOI10.1007/s00453-011-9540-3zbMath1236.68076OpenAlexW2180689556MaRDI QIDQ2429344

K. R. Jampani, Ashkan Aazami, Joseph Cheriyan

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9540-3

zbMATH Keywords

planar graphspackingNP-hardapproximation algorithmsSteiner treeshardness of approximationedge connectivityelement connectivitypartition connectivity

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) 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) Approximation algorithms (68W25)

Related Items

On Element-Connectivity Preserving Graph Simplification ⋮ Reliability assessment of the divide-and-swap cube in terms of generalized connectivity ⋮ The \(\kappa_k\)-connectivity of line graphs ⋮ Unnamed Item ⋮ Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems

Cites Work

• Lower bound of the Hadwiger number of graphs by their average degree
• Packing of Steiner trees and \(S\)-connectors in graphs
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• An approximate max-Steiner-tree-packing min-Steiner-cut theorem
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• The Steiner tree packing problem in VLSI design
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• Packing Steiner trees: Further facets
• Packing Steiner trees: Polyhedral investigations
• Packing Steiner trees: A cutting plane algorithm and computational results
• On the complexity of the disjoint paths problem
• Hardness and approximation results for packing Steiner trees
• Packing Steiner trees with identical terminal sets
• Exact and approximate balanced data gathering in energy-constrained sensor networks
• Multiflow Feasibility: An Annotated Tableau
• Disjoint bases in a polymatroid
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• An extremal function for contractions of graphs
• A Graph Reduction Step Preserving Element-Connectivity and Applications
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
• Packing Steiner Trees: Separation Algorithms
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Minimum partition of a matroid into independent subsets
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item