ISSN:
1432-0541
Schlagwort(e):
Steiner trees
;
Gilbert-Pollak conjecture
;
Subexponential algorithms
;
Regular polytopes
;
Sensitivity diagrams
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract This paper has two purposes. The first is to present a new way to find a Steiner minimum tree (SMT) connectingN sites ind-space,d 〉- 2. We present (in Appendix 1) a computer code for this purpose. This is the only procedure known to the author for finding Steiner minimal trees ind-space ford 〉 2, and also the first one which fits naturally into the framework of “backtracking” and “branch-and-bound.” Finding SMTs of up toN = 12 general sites ind-space (for anyd) now appears feasible. We tabulate Steiner minimal trees for many point sets, including the vertices of most of the regular and Archimedeand-polytopes with 〈- 16 vertices. As a consequence of these tables, the Gilbert-Pollak conjecture is shown to be false in dimensions 3–9. (The conjecture remains open in other dimensions; it is probably false in all dimensionsd withd ≥ 3, but it is probably true whend = 2.) The second purpose is to present some new theoretical results regarding the asymptotic computational complexity of finding SMTs to precision ɛ. We show that in two-dimensions, Steiner minimum trees may be found exactly in exponential time O(C N ) on a real RAM. (All previous provable time bounds were superexponential.) If the tree is only wanted to precision ɛ, then there is an (N/ɛ)O(√N)-time algorithm, which is subexponential if 1/ɛ grows only polynomially withN. Also, therectilinear Steiner minimal tree ofN points in the plane may be found inN O(√N) time. J. S. Provan devised an O(N 6/ɛ4)-time algorithm for finding the SMT of a convexN-point set in the plane. (Also the rectilinear SMT of such a set may be found in O(N 6) time.) One therefore suspects that this problem may be solved exactly in polynomial time. We show that this suspicion is in fact true—if a certain conjecture about the size of “Steiner sensitivity diagrams” is correct. All of these algorithms are for a “real RAM” model of computation allowing infinite precision arithmetic. They make no probabilistic or other assumptions about the input; the time bounds are valid in the worst case; and all our algorithms may be implemented with a polynomial amount of space. Only algorithms yielding theexact optimum SMT, or trees with lengths ≤ (1 + ɛ) × optimum, where ɛ is arbitrarily small, are considered here.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01758756
Permalink
