๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Rectilinear full Steiner tree generation

โœ Scribed by Zachariasen, Martin

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
353 KB
Volume
33
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

The fastest exact algorithm (in practice) for the rectilinear Steiner tree problem in the plane uses a two-phase scheme: First, a small but sufficient set of full Steiner trees (FSTs) is generated and then a Steiner minimum tree is constructed from this set by using simple backtrack search, dynamic programming, or an integer programming formulation. FST generation methods can be seen as problemreduction algorithms and are also useful as a first step in providing good upper and lower bounds for large instances. Currently, the time needed to generate FSTs poses a significant overhead for FST-based exact algorithms. In this paper, we present a very efficient algorithm for the rectilinear FST generation problem which removes this overhead completely. Based on information obtained in a preprocessing phase, the new algorithm ''grows'' FSTs while applying several new and important optimality conditions. For randomly generated instances, approximately 4n FSTs are generated (where n is the number of terminals). The observed running time is quadratic and the FSTs for a 10,000 terminal instance can, on average, be generated within 5 minutes.

๐Ÿ“œ SIMILAR VOLUMES

Full Minimal Steiner Trees on Lattice Se
Full Minimal Steiner Trees on Lattice Sets
โœ M. Brazil; J.H. Rubinstein; D.A. Thomas; J.F. Weng; N.C. Wormald ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 497 KB

Given a finite set of points P in the Euclidean plane, the Steiner problem asks us to constuct a shortest possible network interconnecting P. Such a network is known as a minimal Steiner tree. The Steiner problem is an intrinsically difficult one, having been shown to be NP-hard [7]; however, it oft

A polynomial time algorithm for rectilin
A polynomial time algorithm for rectilinear Steiner trees with terminals constrained to curves
โœ Brazil, M.; Thomas, D. A.; Weng, J. F. ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 168 KB ๐Ÿ‘ 2 views

The rectilinear Steiner problem is the problem of constructing the shortest rectilinear network in the plane connecting a given set of points, called terminals. The problem is known to be NP-complete in general. In this paper, we show that there is a polynomial time algorithm for solving the rectili