Dealing with large hidden constants: engineering a planar Steiner tree PTAS

DOI10.1137/1.9781611972894.12MaRDI QIDQ5233571zbMATH OpenOpenAlexWikidataFDO

Authors Siamak Tazari, Matthias Müller-Hannemann

Publication date 11 September 2019

Published in 2009 Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611972894.12

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Dealing with large hidden constants, engineering a planar Steiner tree PTAS
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
• Strong Steiner tree approximations in practice
• A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane
• A near linear time approximation scheme for Steiner tree among obstacles in the plane

Cited in

(1)

• Dealing with large hidden constants, engineering a planar Steiner tree PTAS

This page was built for publication: Dealing with large hidden constants: engineering a planar Steiner tree PTAS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233571)