✦ LIBER ✦

A note on the terminal Steiner tree problem

✍ Scribed by Bernhard Fuchs

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 53 KB
Volume: 87
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(03)00285-0

No coin nor oath required. For personal study only.

✦ Synopsis

In 2002, Lin and

Xue [Inform. Process. Lett. 84 (2002)

103-107] introduced a variant of the graph Steiner tree problem, in which each terminal vertex is required to be a leaf in the solution Steiner tree. They presented a ρ + 2 approximation algorithm, where ρ is the approximation ratio of the best known efficient algorithm for the regular graph Steiner tree problem. In this note, we derive a simplified algorithm with an improved approximation ratio of 2ρ (currently ρ ≈ 1.550, see [SODA 2000[SODA , 2000, pp. 770-790], pp. 770-790]).

📜 SIMILAR VOLUMES

On the terminal Steiner tree problem

✍ Guohui Lin; Guoliang Xue 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 69 KB

We investigate a practical variant of the well-known graph Steiner tree problem. In this variant, every target vertex is required to be a leaf vertex in the solution Steiner tree. We present hardness results for this variant as well as a polynomial time approximation algorithm with performance ratio

A note on Steiner tree games

✍ Darko Skorin-Kapov; Jadranka Skorin-Kapov 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

The Steiner tree problem

✍ Dirk van Oudheusden 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 87 KB

The Steiner tree problem for terminals o

The Steiner tree problem for terminals on the boundary of a rectilinear polygon

✍ Siu-Wing Cheng 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 233 KB

Given a simple rectilinear polygon P with k sides and n terminals on its boundary, we present an O(k 3 n)-time algorithm to compute the minimal rectilinear Steiner tree lying inside P interconnecting the terminals. We obtain our result by proving structural properties of a selective set of minimal S

A constrained Steiner tree problem

✍ Moshe B. Rosenwein; Richard T. Wong 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 645 KB

The 1-steiner tree problem

✍ George Georgakopoulos; Christos H Papadimitriou 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 480 KB