Title: Obstacle-Avoiding Rectilinear Steiner Tree Construction: A Steiner-Point-Based Algorithm
Abstract: For the obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem, we present a Steiner-point-based algorithm that achieves the best practical performance among existing heuristics. We first propose a new concept of Steiner point locations, creating a linear-space routing graph with satisfactory Steiner point candidates to resolve the bottleneck of most existing heuristics. Then, we propose a Steiner-point-based framework to yield a solution, which is close to the key to the handling of the OARSMT problem. Experimental results show that this algorithm achieves excellent solution quality and speed performance at the same time. We also extend the Steiner-point-based framework to the obstacle-avoiding preferred direction Steiner tree problem with a good performance.
Publication Year: 2012
Publication Date: 2012-07-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 30
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot