A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane

DOI10.1007/978-3-540-73951-7_14MaRDI QIDQ3603523zbMATH OpenOpenAlexFDO

Authors Siamak Tazari, Matthias Müller-Hannemann

Publication date 17 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73951-7_14

zbMATH Keywords

obstaclesplanar graphspannerEuclidean metricSteiner treePTASuniform orientation metricBanyan

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• A near linear time approximation scheme for Steiner tree among obstacles in the plane
• An Approximation Scheme for Finding Steiner Trees with Obstacles
• An approximation scheme for some Steiner tree problems in the plane
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
• scientific article; zbMATH DE number 1555959

Cited in

(10)

• An Approximation Scheme for Finding Steiner Trees with Obstacles
• A near linear time approximation scheme for Steiner tree among obstacles in the plane
• scientific article; zbMATH DE number 1985307 (Why is no real title available?)
• Simplifying obstacles for Steiner network problems in the plane
• Dealing with large hidden constants: engineering a planar Steiner tree PTAS
• Dealing with large hidden constants, engineering a planar Steiner tree PTAS
• Rectilinear paths with minimum segment lengths
• An O(n n) approximation scheme for Steiner tree in planar graphs
• A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon

This page was built for publication: A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane

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