𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation algorithm for bottleneck Steiner tree problem in the Euclidean plane

✍ Scribed by Zi-Mao Li; Da-Ming Zhu; Shao-Han Ma

Publisher
Springer
Year
2004
Tongue
English
Weight
339 KB
Volume
19
Category
Article
ISSN
1000-9000

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

A Polylogarithmic Approximation Algorith
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
✍ Naveen Garg; Goran Konjevod; R. Ravi πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 130 KB

The group Steiner tree problem is a generalization of the Steiner tree problem where we are given several subsets (groups) of vertices in a weighted graph, and the goal is to find a minimum-weight connected subgraph containing at least one vertex from each group.The problem was introduced by Reich a

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.