ObSteiner: An Exact Algorithm for the Construction of Rectilinear Steiner Minimum Trees in the Presence of Complex Rectilinear Obstacles
Publication in refereed journal


引用次數
替代計量分析
.

其它資訊
摘要In this paper, we present ObSteiner, an exact algorithm for the construction of obstacle-avoiding rectilinear Steiner minimum trees (OARSMTs) among complex rectilinear obstacles. This is the first paper to propose a geometric approach to optimally solve the OARSMT problem among complex obstacles. The optimal solution is constructed by the concatenation of full Steiner trees among complex obstacles, which are proven to be of simple structures in this paper. ObSteiner is able to handle complex obstacles, including both convex and concave ones. Benchmarks with hundreds of terminals among a large number of obstacles are solved optimally in a reasonable amount of time.
著者Huang T, Young EFY
期刊名稱IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
出版年份2013
月份6
日期1
卷號32
期次6
出版社IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
頁次882 - 893
國際標準期刊號0278-0070
電子國際標準期刊號1937-4151
語言英式英語
關鍵詞Full Steiner tree (FST); obstacle avoiding; rectilinear Steiner minimum tree (OARSMT); routing
Web of Science 學科類別Computer Science; Computer Science, Hardware & Architecture; COMPUTER SCIENCE, HARDWARE & ARCHITECTURE; Computer Science, Interdisciplinary Applications; COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS; Engineering; Engineering, Electrical & Electronic; ENGINEERING, ELECTRICAL & ELECTRONIC

上次更新時間 2020-01-12 於 00:28