✦ LIBER ✦

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

✍ Scribed by Siu-Wing Cheng

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 233 KB
Volume: 237
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(98)00171-6

No coin nor oath required. For personal study only.

✦ Synopsis

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 Steiner trees and exploiting them in a dynamic programming algorithm.

📜 SIMILAR VOLUMES

Reductions for the rectilinear steiner t

Reductions for the rectilinear steiner tree problem

✍ Pawel Winter 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 842 KB

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 the terminal Steiner tree prob

A note on the terminal Steiner tree problem

✍ Bernhard Fuchs 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 53 KB

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 bes

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 tabu search heuristic for the Steiner

A tabu search heuristic for the Steiner Tree Problem

✍ Gendreau, Michel; Larochelle, Jean-Francois; Sans�, Brunilde 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 342 KB 👁 2 views

The Steiner Tree Problem (STP) in graphs is a well-known NP-hard problem. It has regained attention due to the introduction of new telecommunication technologies, such as ATM, since it appears as the inherent mathematical structure behind multicast communications. In this paper, we present a tabu se

Probabilistic models for the Steiner Tre

Probabilistic models for the Steiner Tree problem

✍ Vangelis Th. Paschos; Orestis A. Telelis; Vassilis Zissimopoulos 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 216 KB