๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Approximations for two variants of the Steiner tree problem in the Euclidean plane({mathbb{R}^2})

โœ Scribed by Jianping Li, Haiyan Wang, Binchao Huang, Junran Lichen

Book ID
120703899
Publisher
Springer US
Year
2012
Tongue
English
Weight
312 KB
Volume
57
Category
Article
ISSN
0925-5001

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

An approximation algorithm for a bottlen
An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane
โœ Lusheng Wang; Zimao Li ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 95 KB

We study a bottleneck Steiner tree problem: given a set P = {p 1 , p 2 , . . . , p n } of n terminals in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. The problem has applications in

An approximation scheme for some Steiner
An approximation scheme for some Steiner tree problems in the plane
โœ Wang, Lusheng; Jiang, Tao ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 536 KB

We design a polynomial-time approximation scheme for the Steiner tree problem in the plane when the given set of regular points is c-local, i.e., in the minimum-cost spanning tree for the given set of regular points, the length of the longest edge is at most c times the length of the shortest edge.

Experimental evaluation of a partitionin
Experimental evaluation of a partitioning algorithm for the steiner tree problem in R2 and R3
โœ Sivakumar Ravada; Alan T. Sherman ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 614 KB

## Abstract We experimentally evaluate sequential and distributed implementations of an approximation partitioning algorithm by Kalpakis and Sherman for the __Geometric Steiner Minimum Tree Problem (GSMT)__ in __R^d^__ for __d__ = 2,3. Our implementations incorporate an improved method for combinin