𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Faster exact algorithms for steiner trees in planar networks

✍ Scribed by Marshall Bern

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
739 KB
Volume
20
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

Exact boundary controllability of nodal
Exact boundary controllability of nodal profile for quasilinear hyperbolic systems in a tree-like network
✍ Qilong Gu; Tatsien Li πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 263 KB

In this paper, the exact boundary controllability of nodal profile is established for quasilinear hyperbolic systems with general nonlinear boundary and interface conditions in a tree-like network with general topology. The basic principles for giving nodal profiles and for choosing boundary control

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

Efficient Parallel Algorithms for Optima
Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network
✍ Biing-Feng Wang πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 128 KB

In this paper, we propose efficient parallel algorithms on the EREW PRAM for optimally locating in a tree network a path-shaped facility and a tree-shaped facility of a specified length. Edges in the tree network have arbitrary positive lengths. Two optimization criteria are considered: minimum ecce