An approximation scheme for some Steiner tree problems in the plane

DOI10.1002/(SICI)1097-0037(199612)28:4%3C187::AID-NET3%3E3.0.CO;2-HMaRDI QIDQ4344454zbMATH OpenOpenAlexFDO

Authors Lusheng Wang, Tao Jiang

Publication date 15 July 1997

Full work available at URL https://doi.org/10.1002/(sici)1097-0037(199612)28:4%3C187::aid-net3%3E3.0.co;2-h

zbMATH Keywords

polynomial-time approximation schemeSteiner tree problemminimum-cost spanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 1555959
• Improved Approximations for the Steiner Tree Problem
• scientific article; zbMATH DE number 742979
• New approximation algorithms for the Steiner tree problems
• Approximations for Steiner trees with minimum number of Steiner points

Cited in

(25)

• scientific article; zbMATH DE number 1555959 (Why is no real title available?)
• Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
• PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
• Numerical approximation of the Steiner problem in dimension 2 and 3
• THE EFFECT OF ASYMMETRY ON THE ON-LINE MULTICAST ROUTING PROBLEM
• Approximations for Steiner trees with minimum number of Steiner points
• PTAS for connected vertex cover in unit disk graphs
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• 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
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• Approximations for Steiner trees with minimum number of Steiner points
• Generalised \(k\)-Steiner tree problems in normed planes
• An O(n n) approximation scheme for Steiner tree in planar graphs
• A polynomial time approximation scheme for the grade of service Steiner minimum tree problem
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation schemes for node-weighted geometric Steiner tree problems
• Extending the kernel for planar Steiner tree to the number of Steiner vertices
• A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
• Improved Approximations for the Steiner Tree Problem
• scientific article; zbMATH DE number 742979 (Why is no real title available?)
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon

This page was built for publication: An approximation scheme for some Steiner tree problems in the plane

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