ISSN:
1432-0541
Keywords:
Spanning tree
;
Steiner tree
;
Heuristic algorithm
;
Geometric probability
;
Optimization
;
Graph
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract In recent years, researchers have proven many theorems of the following form: given points distributed according to a Poisson process with intensity parameterN on the unit square, the length of the shortest spanning tree (rectilinear Steiner tree, traveling salesman tour, or some other functional) on these points is, with probability one, asymptotic to β√N for some constant β (which is presumably different for different functionals). Though these theorems are well understood, very little is known about the constants β. In this paper we prove that the constants in the cases of rectilinear spanning tree and rectilinear Steiner tree do, indeed, differ. This proof is constructive in the sense that we give a polynomial-time heuristic algorithm that produces a Steiner tree of expected length some fraction shorter than a minimum spanning tree. We continue the analysis to prove a second result: the expected value of the minimum number of Steiner points in a shortest rectilinear Steiner tree grows linearly withN.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01762114
Permalink
