Obstacle-avoiding Rectilinear Steiner Minimum Tree Construction: An Optimal Approach
Refereed conference paper presented and published in conference proceedings


Times Cited
Web of Science16WOS source URL (as at 19/02/2021) Click here for the latest count
Altmetrics Information
.

Other information
AbstractIn this paper, we present an efficient method to solve the obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem optimally. Our work is a major improvement over the work proposed in [1]. First, a new kind of full Steiner trees (FSTs) called obstacle-avoiding full Steiner trees (OAFSTs) is proposed. We show that for any OARSMT problem there exists an optimal tree composed of OAFSTs only. We then extend the proofs on the possible topologies of FSTs in [2] to find the possible topologies of OAFSTs, showing that OAFSTs can be constructed easily. A two-phase algorithm for the construction of OARSMTs is then developed. In the first phase, a sufficient number of OAFSTs are generated. In the second phase, the OAFSTs are used to construct an OARSMT. Experimental results on several benchmarks show that the proposed method achieves 185 times speedup on average and is able to solve more benchmarks than the approach in [1].
All Author(s) ListHuang T, Young EFY
Name of ConferenceIEEE and ACM International Conference on Computer-Aided Design
Start Date of Conference07/11/2010
End Date of Conference11/11/2010
Place of ConferenceSan Jose
Country/Region of ConferenceUnited States of America
Detailed descriptionorganized by IEEE/ACM,
Year2010
Month1
Day1
PublisherIEEE
Pages610 - 613
eISBN978-1-4244-8192-7
ISSN1933-7760
LanguagesEnglish-United Kingdom
Web of Science Subject CategoriesComputer Science; Computer Science, Theory & Methods; Engineering; Engineering, Electrical & Electronic

Last updated on 2021-19-02 at 23:58