A near linear time approximation scheme for Steiner tree among obstacles in the plane

DOI10.1016/J.COMGEO.2009.01.011zbMATH Open1215.05189OpenAlexW2087083181WikidataQ57013199 ScholiaQ57013199MaRDI QIDQ2269141FDOQ2269141

Authors: Siamak Tazari, Matthias Müller-Hannemann 

Publication date: 16 March 2010

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2009.01.011

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

zbMATH Keywords

obstaclesplanar graphspannerEuclidean metricSteiner treePTASbanyanuniform orientation metric

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• The Steiner problem in phylogeny is NP-complete
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• The Steiner tree problem
• Planar spanners and approximate shortest path queries among obstacles in the plane
• Steiner Minimal Trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation of rectilinear Steiner trees with length restrictions on obstacles.
• The Steiner problem with edge lengths 1 and 2
• Title not available (Why is that?)
• Title not available (Why is that?)
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
• Title not available (Why is that?)
• On Steiner Minimal Trees with Rectilinear Distance
• Title not available (Why is that?)
• On Steiner’s Problem with Rectilinear Distance
• Title not available (Why is that?)
• Une heuristique pour le problème de l'arbre de Steiner
• An Approximation Scheme for Finding Steiner Trees with Obstacles
• Minimum networks in uniform orientation metrics
• Title not available (Why is that?)
• Approximation of Octilinear Steiner Trees Constrained by Hard and Soft Obstacles
• HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES

Cited In (10)

• An exact algorithm for constructing minimum Euclidean skeletons of polygons
• An Approximation Scheme for Finding Steiner Trees with Obstacles
• An O ( n log n ) approximation scheme for Steiner tree in planar graphs
• A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane
• Title not available (Why is that?)
• Dealing with large hidden constants: engineering a planar Steiner tree PTAS
• Dealing with large hidden constants, engineering a planar Steiner tree PTAS
• Approximation algorithms for network design problems
• 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 Q2269141)