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

DOI10.1007/S00453-011-9540-3zbMATH Open1236.68076OpenAlexW2180689556MaRDI QIDQ2429344FDOQ2429344

Authors: Ashkan Aazami, K. R. Jampani, 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

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

zbMATH Keywords

approximation algorithmsNP-hardpackingplanar graphshardness of approximationSteiner treesedge connectivityelement connectivitypartition connectivity

Mathematics Subject Classification ID

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)

Cites Work

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

Cited In (15)

• Title not available (Why is that?)
• Packing element-disjoint steiner trees
• A graph reduction step preserving element-connectivity and packing Steiner trees and forests
• 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
• Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs
• Reliability assessment of the divide-and-swap cube in terms of generalized connectivity
• On element-connectivity preserving graph simplification
• Algorithms – ESA 2004
• The \(\kappa_k\)-connectivity of line graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Hardness and approximation results for packing Steiner trees
• \(1\)-line minimum rectilinear Steiner trees and related problems

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)