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


引用次數
替代計量分析
.

其它資訊
摘要In 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].
著者Huang T, Young EFY
會議名稱IEEE and ACM International Conference on Computer-Aided Design
會議開始日07.11.2010
會議完結日11.11.2010
會議地點San Jose
會議國家/地區美國
詳細描述organized by IEEE/ACM,
出版年份2010
月份1
日期1
出版社IEEE
頁次610 - 613
電子國際標準書號978-1-4244-8192-7
國際標準期刊號1933-7760
語言英式英語
Web of Science 學科類別Computer Science; Computer Science, Theory & Methods; Engineering; Engineering, Electrical & Electronic

上次更新時間 2021-11-04 於 23:39