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

DOI10.1145/1806689.1806720zbMath1293.68308OpenAlexW1982089707MaRDI QIDQ2875147

MohammadHossein Bateni, Dániel Marx, Mohammad Taghi 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 graphsseries-parallel graphsPTASSteiner forestbounded-genus graphsbounded-treewidth graphs

Mathematics Subject Classification ID

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

Related Items (8)

Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs ⋮ Improved Steiner tree algorithms for bounded treewidth ⋮ Euclidean prize-collecting Steiner forest ⋮ 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 ⋮ Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth