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

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)

• A polynomial-time approximation scheme for planar multiway cut
• The Steiner forest problem revisited
• 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
• 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
• An O(n n) approximation scheme for Steiner tree in planar graphs
• scientific article; zbMATH DE number 7053305 (Why is no real title available?)
• 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

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)