𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Reductions for the rectilinear steiner tree problem

✍ Scribed by Pawel Winter

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
842 KB
Volume
26
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

The Steiner tree problem
The Steiner tree problem
✍ Dirk van Oudheusden πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 87 KB
Delay-related secondary objectives for r
Delay-related secondary objectives for rectilinear Steiner minimum trees
✍ Sven Peyer; Martin Zachariasen; David Grove JΓΈrgensen πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 759 KB

The rectilinear Steiner tree problem in the plane is to construct a minimum-length tree interconnecting a set of points (called terminals) consisting of horizontal and vertical line segments only. Rectilinear Steiner minimum trees (RSMTs) can today be computed quickly for realistic instances occurri