Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
DOI10.1145/1806689.1806720zbMATH Open1293.68308OpenAlexW1982089707MaRDI QIDQ2875147FDOQ2875147
Authors: MohammadHossein Bateni, Dániel Marx, Mohammad T. Hajiaghayi 
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806720
Recommendations
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- scientific article; zbMATH DE number 6783450
- Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
- Network sparsification for Steiner problems on planar and bounded-genus graphs
- Euclidean prize-collecting Steiner forest
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) 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)
Cited In (15)
- The Steiner forest problem revisited
- An O ( n log n ) approximation scheme for Steiner tree in planar graphs
- A PTAS for weight constrained Steiner trees in series--parallel graphs.
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Euclidean prize-collecting Steiner forest
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Network sparsification for Steiner problems on planar and bounded-genus graphs
- Improved Steiner tree algorithms for bounded treewidth
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Title not available (Why is that?)
- Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
- Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
- Linear-time computation of a linear problem kernel for dominating set on planar graphs
- A polynomial-time approximation scheme for planar multiway cut
This page was built for publication: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875147)
