𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximating minimum Steiner point trees in Minkowski planes

✍ Scribed by M. Brazil; C. J. Ras; D. A. Thomas

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
244 KB
Volume
56
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Approximating Steiner trees in graphs wi
Approximating Steiner trees in graphs with restricted weights
✍ HalldοΏ½rsson, MagnοΏ½s M.; Ueno, Shuichi; Nakao, Hiroshi; Kajitani, Yoji πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 128 KB πŸ‘ 2 views

We analyze the approximation ratio of the average distance heuristic for the Steiner tree problem on graphs and prove nearly tight bounds for the cases of complete graphs with binary weights {1, d} or weights in the interval [1, d], where d Β°2. The improvement over other analyzed algorithms is a fac

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.

Approximating the Minimum-Degree Steiner
Approximating the Minimum-Degree Steiner Tree to within One of Optimal
✍ M. Furer; B. Raghavachari πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 691 KB

The problem of constructing a spanning tree for a graph \(G=(V, E)\) with \(n\) vertices whose maximal degree is the smallest among all spanning trees of \(G\) is considered. This problem is easily shown to be NP-hard. In the Steiner version of this problem, along with the input graph, a set of dist

A tight lower bound for the Steiner rati
A tight lower bound for the Steiner ratio in Minkowski planes
✍ Biao Gao; Ding-Zhu Du; Ronald L. Graham πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 804 KB

A minimum Steiner tree for a given set X of points is a network interconnecting the points of X having minimum possible total length. The Steiner ratio for a metric space is the largest lower bound for the ratio of lengths between a minimum Steiner tree and a minimum spanning tree on the same set of