A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting

DOI10.1145/2897518.2897549zbMath1376.68168OpenAlexW2415335518MaRDI QIDQ5361862

Dániel Marx, Erik D. Demaine, MohammadHossein Bateni, Mohammad Taghi Hajiaghayi

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2897518.2897549

zbMATH Keywords

approximation algorithmplanar graphsPTASgroup Steiner tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) 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 (2)

A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ A PTAS for the Steiner Forest Problem in Doubling Metrics

This page was built for publication: A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting