Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth

DOI10.1145/1806689.1806720MaRDI QIDQ2875147zbMATHOpenAlexFDO

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

zbMATH Keywords

planar graphsPTASSteiner forestseries-parallel graphsbounded-genus graphsbounded-treewidth graphs

Mathematics Subject Classification ID

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)

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

Cited in

(15)

• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• A PTAS for weight constrained Steiner trees in series--parallel graphs.
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Network sparsification for Steiner problems on planar and bounded-genus graphs
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• An \(O(n\log n)\) approximation scheme for Steiner tree in planar graphs
• Linear-time computation of a linear problem kernel for dominating set on planar graphs
• Euclidean prize-collecting Steiner forest
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• The Steiner forest problem revisited
• A polynomial-time approximation scheme for planar multiway cut
• Improved Steiner tree algorithms for bounded treewidth
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• scientific article; zbMATH DE number 7053305 (Why is no real title available?)

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)