✦ LIBER ✦

On efficient implementation of an approximation algorithm for the Steiner tree problem

✍ Scribed by Lawrence T. Kou

Publisher: Springer-Verlag
Year: 1990
Tongue: English
Weight: 689 KB
Volume: 27
Category: Article
ISSN: 0001-5903
DOI: 10.1007/bf00264613

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

A faster approximation algorithm for the

A faster approximation algorithm for the steiner tree problem in graphs

✍ Alexander Z. Zelikovsky 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 369 KB

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

On the approximability of the Steiner tr

On the approximability of the Steiner tree problem

✍ Martin Thimm 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 165 KB

We show that it is not possible to approximate the minimum Steiner tree problem within 1 + 1 162 unless RP = NP. The currently best known lower bound is 1 + 1 400 . The reduction is from H astad's nonapproximability result for maximum satisÿability of linear equation modulo 2. The improvement on the

A New Approximation Algorithm for the St

A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3

✍ Hans Jürgen Prömel; Angelika Steger 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 100 KB

In this paper we present an RNC approximation algorithm for the Steiner tree problem in graphs with performance ratio 5r3 and RNC approximation algorithms for the Steiner tree problem in networks with performance ratio 5r3 q ⑀ for all ⑀ ) 0. This is achieved by considering a related problem, the min

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.