The rectilinear Steiner tree problem involves finding the shortest network connecting a given terminal set along rectilinear grid lines. We develop algorithms using randomly selected permutations of the terminal set and we show that for small terminal sets better results are obtained by the randomly selected permutations than by well-known algorithms. We prove that for n≤6 all terminal sets may be minimally connected by considering all permutations and that for n≤9 there is a set of terminals that cannot be minimally connected by considering all permutations of the terminals. For these n≤9 benchmark examples, shorter length trees are obtained by the randomly-selected permutation algorithm than by well-known algorithms.
|Title of host publication||Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999|
|ISBN (Electronic)||1581131283, 9781581131284|
|State||Published - Apr 1 1999|
|Event||37th Annual Southeast Regional Conference, ACM-SE 1999 - Mobile, United States|
Duration: Apr 15 1999 → Apr 18 1999
|Name||Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999|
|Conference||37th Annual Southeast Regional Conference, ACM-SE 1999|
|Period||4/15/99 → 4/18/99|
Bibliographical notePublisher Copyright:
© 1999 ACM.
ASJC Scopus subject areas
- Computational Theory and Mathematics
- Computer Science Applications
- Hardware and Architecture