An approximation scheme for some Steiner tree problems in the plane

DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1097-0037(199612)28:4<187::AID-NET3>3.0.CO;2-H" /><187::AID-NET3>3.0.CO;2-H 10.1002/(SICI)1097-0037(199612)28:4<187::AID-NET3>3.0.CO;2-HzbMath0873.90106OpenAlexW1981466335MaRDI QIDQ4344454

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<187::aid-net3>3.0.co;2-h

zbMATH Keywords

Steiner tree problempolynomial-time approximation schememinimum-cost spanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (10)

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 ⋮ PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs ⋮ A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks ⋮ THE EFFECT OF ASYMMETRY ON THE ON-LINE MULTICAST ROUTING PROBLEM ⋮ Approximations for Steiner trees with minimum number of Steiner points ⋮ A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs ⋮ PTAS for connected vertex cover in unit disk graphs ⋮ Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.

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