𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Canonical Forms and Algorithms for Steiner Trees in Uniform Orientation Metrics

✍ Scribed by M. Brazil; D. A. Thomas; J. F. Weng; M. Zachariasen

Publisher
Springer
Year
2005
Tongue
English
Weight
312 KB
Volume
44
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Forbidden subpaths for Steiner minimum n
Forbidden subpaths for Steiner minimum networks in uniform orientation metrics
✍ M. Brazil; D. A. Thomas; J. F. Weng πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 260 KB

## Abstract The Steiner problem in the λ‐plane is the problem of constructing a minimum network connecting a given set of nodes (called terminals), with the constraint that all line segments have slopes chosen from the Ξ» uniform orientation angles Ο‰, 2Ο‰, … , λω, where Ο‰ = Ο€/Ξ». This problem appears

Faster exact algorithms for steiner tree
Faster exact algorithms for steiner trees in planar networks
✍ Marshall Bern πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 739 KB

We improve the time and space complexities of dynamic programming algorithms that compute optimal Steiner trees spanning nodes in planar networks. Our algorithms have special application to the rectilinear Steiner problem.

Experimental evaluation of a partitionin
Experimental evaluation of a partitioning algorithm for the steiner tree problem in R2 and R3
✍ Sivakumar Ravada; Alan T. Sherman πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 614 KB

## Abstract We experimentally evaluate sequential and distributed implementations of an approximation partitioning algorithm by Kalpakis and Sherman for the __Geometric Steiner Minimum Tree Problem (GSMT)__ in __R^d^__ for __d__ = 2,3. Our implementations incorporate an improved method for combinin