An Edge-Based Heuristic for Steiner Routing

Manjit Borah; Robert Michael Owens; Mary Jane Irwin

doi:10.1109/43.331412

An Edge-Based Heuristic for Steiner Routing

Manjit Borah, Robert Michael Owens, Mary Jane Irwin

Research output: Contribution to journal › Article › peer-review

93 Scopus citations

Abstract

A new approximation heuristic for finding a rectilinear Steiner tree of a set of nodes is presented. It starts with a rectilinear minimum spanning tree of the nodes and repeatedly connects a node to the nearest point on the rectangular layout of an edge, removing the longest edge of the loop thus formed. A simple implementation of the heuristic using conventional data structures is compared with previously existing algorithms. The performance (i.e., quality of the route produced) of our algorithm is as good as the best reported algorithm, while the running time is an order of magnitude better than that of this best algorithm. It is also shown that the asymptotic time complexity for the algorithm can be improved to 0(n log n), where n is the number of points in the set.

Original language	English (US)
Pages (from-to)	1563-1568
Number of pages	6
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	13
Issue number	12
DOIs	https://doi.org/10.1109/43.331412
State	Published - Dec 1994

All Science Journal Classification (ASJC) codes

Software
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering

Access to Document

10.1109/43.331412

Cite this

@article{893918d8c14f4f47ae5d12d5d36fe200,

title = "An Edge-Based Heuristic for Steiner Routing",

abstract = "A new approximation heuristic for finding a rectilinear Steiner tree of a set of nodes is presented. It starts with a rectilinear minimum spanning tree of the nodes and repeatedly connects a node to the nearest point on the rectangular layout of an edge, removing the longest edge of the loop thus formed. A simple implementation of the heuristic using conventional data structures is compared with previously existing algorithms. The performance (i.e., quality of the route produced) of our algorithm is as good as the best reported algorithm, while the running time is an order of magnitude better than that of this best algorithm. It is also shown that the asymptotic time complexity for the algorithm can be improved to 0(n log n), where n is the number of points in the set.",

author = "Manjit Borah and Owens, {Robert Michael} and Irwin, {Mary Jane}",

year = "1994",

month = dec,

doi = "10.1109/43.331412",

language = "English (US)",

volume = "13",

pages = "1563--1568",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "12",

}

TY - JOUR

T1 - An Edge-Based Heuristic for Steiner Routing

AU - Borah, Manjit

AU - Owens, Robert Michael

AU - Irwin, Mary Jane

PY - 1994/12

Y1 - 1994/12

N2 - A new approximation heuristic for finding a rectilinear Steiner tree of a set of nodes is presented. It starts with a rectilinear minimum spanning tree of the nodes and repeatedly connects a node to the nearest point on the rectangular layout of an edge, removing the longest edge of the loop thus formed. A simple implementation of the heuristic using conventional data structures is compared with previously existing algorithms. The performance (i.e., quality of the route produced) of our algorithm is as good as the best reported algorithm, while the running time is an order of magnitude better than that of this best algorithm. It is also shown that the asymptotic time complexity for the algorithm can be improved to 0(n log n), where n is the number of points in the set.

AB - A new approximation heuristic for finding a rectilinear Steiner tree of a set of nodes is presented. It starts with a rectilinear minimum spanning tree of the nodes and repeatedly connects a node to the nearest point on the rectangular layout of an edge, removing the longest edge of the loop thus formed. A simple implementation of the heuristic using conventional data structures is compared with previously existing algorithms. The performance (i.e., quality of the route produced) of our algorithm is as good as the best reported algorithm, while the running time is an order of magnitude better than that of this best algorithm. It is also shown that the asymptotic time complexity for the algorithm can be improved to 0(n log n), where n is the number of points in the set.

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

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

U2 - 10.1109/43.331412

DO - 10.1109/43.331412

M3 - Article

AN - SCOPUS:0028733612

SN - 0278-0070

VL - 13

SP - 1563

EP - 1568

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 12

ER -

An Edge-Based Heuristic for Steiner Routing

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this