@inproceedings{3626a6f598d841a381a6fd2414f9a4bf,
title = "Obstacle-avoiding rectilinear Steiner tree construction based on Steiner point selection",
abstract = "For the obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem, this paper presents a Steiner-point based algorithm to achieve the best practical performance in wirelength and run time. Unlike many previous works, the Steiner-based framework is more focused on the usage of Steiner points instead of the handling of obstacles. This paper also proposes a new concept of Steiner point locations to provide an effective as well as efficient way to generate desirable Steiner point candidates. Experimental results show that this algorithm achieves the best solution quality in Θ(n log n) empirical time, which was originally generated by applying the maze routing on an Ω(n2)-space graph. The Steiner-point based framework and the new concept of Steiner point locations can be applied to future research on the OARSMT problem and its generations, such as the multi-layer OARSMT problem.",
keywords = "Physical design, Routing, Spanning tree, Steiner tree",
author = "Liu, \{Chih Hung\} and Yuan, \{Shih Yi\} and Kuo, \{Sy Yen\} and Weng, \{Jung Hung\}",
year = "2009",
doi = "10.1145/1687399.1687406",
language = "英语",
isbn = "9781605588001",
series = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "26--32",
booktitle = "Proceedings of the 2009 IEEE/ACM International Conference on Computer-Aided Design - Digest of Technical Papers, ICCAD 2009",
address = "美国",
note = "2009 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2009 ; Conference date: 02-11-2009 Through 05-11-2009",
}