TY  - JOUR
A1  - Sulimma, Kolja
A1  - Kunz, Wolfgang
T1  - An exact algorithm for solving difficult detailed routing problems
T2  - Proceedings of the 2001 international symposium on Physical design, ISPD’01, April 14, 2001Sonoma, California, S. 198-203 , ISBN: 1-58113-347-2
N2  - Channel routing is an NP-complete problem. Therefore, it is likely that there is no efficient algorithm solving this problem exactly.In this paper, we show that channel routing is a fixed-parameter tractable problem and that we can find a solution in linear time for a fixed channel width.We implemented our approach for the restricted layer model. The algorithm finds an optimal route for channels with up to 13 tracks within minutes or up to 11 tracks within seconds.Such narrow channels occur for example as a leaf problem of hierarchical routers or within standard cell generators.
Y1  - 2006
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/2884
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-25242
SN  - 1-58113-347-2
SP  - 198
EP  - 203
PB  - ACM
ER  -