Obstacle-avoiding rectilinear steiner minimum tree construction: An optimal approach
Refereed conference paper presented and published in conference proceedings

Times Cited
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 And 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]. © 2010 IEEE.
All Author(s) ListHuang T., Young E.F.Y.
Name of Conference2010 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2010
Start Date of Conference07/11/2010
End Date of Conference11/11/2010
Place of ConferenceSan Jose, CA
Country/Region of ConferenceUnited States of America
Detailed descriptionorganized by IEEE,
Pages610 - 613
LanguagesEnglish-United Kingdom

Last updated on 2021-01-03 at 02:10