The rectilinear steiner tree problem: Algorithms and examples using permutations of the terminal set

Christine R. Leverenz; Miroslaw Truszczynski

doi:10.1145/306363.306402

The rectilinear steiner tree problem: Algorithms and examples using permutations of the terminal set

Christine R. Leverenz, Miroslaw Truszczynski

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999
ISBN (Electronic)	1581131283, 9781581131284
DOIs	https://doi.org/10.1145/306363.306402
State	Published - Apr 1 1999
Event	37th Annual Southeast Regional Conference, ACM-SE 1999 - Mobile, United States Duration: Apr 15 1999 → Apr 18 1999

Publication series

Name	Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999

Conference

Conference	37th Annual Southeast Regional Conference, ACM-SE 1999
Country/Territory	United States
City	Mobile
Period	4/15/99 → 4/18/99

Bibliographical note

Publisher Copyright:
© 1999 ACM.

ASJC Scopus subject areas

Software
Computational Theory and Mathematics
Computer Science Applications
Hardware and Architecture

Access to Document

10.1145/306363.306402

Cite this

@inproceedings{02882d2965f0408087fd70b716f743f0,

title = "The rectilinear steiner tree problem: Algorithms and examples using permutations of the terminal set",

abstract = "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.",

author = "Leverenz, {Christine R.} and Miroslaw Truszczynski",

note = "Publisher Copyright: {\textcopyright} 1999 ACM.; 37th Annual Southeast Regional Conference, ACM-SE 1999 ; Conference date: 15-04-1999 Through 18-04-1999",

year = "1999",

month = apr,

day = "1",

doi = "10.1145/306363.306402",

language = "English",

series = "Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999",

booktitle = "Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999",

}

Leverenz, CR & Truszczynski, M 1999, The rectilinear steiner tree problem: Algorithms and examples using permutations of the terminal set. in Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999., a31, Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999, 37th Annual Southeast Regional Conference, ACM-SE 1999, Mobile, United States, 4/15/99. https://doi.org/10.1145/306363.306402

The rectilinear steiner tree problem: Algorithms and examples using permutations of the terminal set. / Leverenz, Christine R.; Truszczynski, Miroslaw.
Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999. 1999. a31 (Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - The rectilinear steiner tree problem

T2 - 37th Annual Southeast Regional Conference, ACM-SE 1999

AU - Leverenz, Christine R.

AU - Truszczynski, Miroslaw

PY - 1999/4/1

Y1 - 1999/4/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85029425095&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85029425095&partnerID=8YFLogxK

U2 - 10.1145/306363.306402

DO - 10.1145/306363.306402

M3 - Conference contribution

AN - SCOPUS:85029425095

T3 - Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999

BT - Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999

Y2 - 15 April 1999 through 18 April 1999

ER -

The rectilinear steiner tree problem: Algorithms and examples using permutations of the terminal set

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this