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

DOI10.1145/1806689.1806720MaRDI QIDQ2875147zbMATH OpenOpenAlexFDO

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

bounded-genus graphsbounded-treewidth graphsplanar graphsPTASseries-parallel graphsSteiner forest

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Dynamic programming (90C39)

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

(16)

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

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)