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

Producción científica: Conference contribution › revisión exhaustiva

2 Citas (Scopus)

Resumen

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.

Idioma original	English
Título de la publicación alojada	Proceedings of the 37th Annual Southeast Regional Conference, ACM-SE 1999
ISBN (versión digital)	1581131283, 9781581131284
DOI	https://doi.org/10.1145/306363.306402
Estado	Published - abr 1 1999
Evento	37th Annual Southeast Regional Conference, ACM-SE 1999 - Mobile, United States Duración: abr 15 1999 → abr 18 1999

Serie de la publicación

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

Conference

Conference	37th Annual Southeast Regional Conference, ACM-SE 1999
País/Territorio	United States
Ciudad	Mobile
Período	4/15/99 → 4/18/99

Nota bibliográfica

Publisher Copyright:
© 1999 ACM.

ASJC Scopus subject areas

Software
Computational Theory and Mathematics
Computer Science Applications
Hardware and Architecture

Acceder al documento

10.1145/306363.306402

Otros archivos y enlaces

Citar esto

@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. En 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).

Producción científica: Conference contribution › revisión exhaustiva

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 - https://www.scopus.com/pages/publications/85029425095

UR - https://www.scopus.com/pages/publications/85029425095#tab=citedBy

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

Resumen

Serie de la publicación

Conference

Nota bibliográfica

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto