Name
Abstract | ||
|---|---|---|
We study the minimum rectilinear Steiner tree problem in the presence of obstacles. Traversing obstacles is not strictly forbidden, but the total length of each connected component in the intersection of the tree with the interior of the blocked area is bounded by a constant. This problem is motivated by the layout of repeater tree topologies, a central task in chip design. Large blockages might be crossed by wires on higher layers, but repeaters may not be placed within the blocked area. A too long unbuffered piece of interconnect would lead to timing violations. We present a 2-approximation algorithm with a worst case running time of O(k log k)^2, where k is the number of terminals plus the number of obstacle corner points. Under mild assumptions on the obstacle structure, as they are prevalent in chip design, the running time is O(k log k)^2. Compared to strictly obstacle-avoiding trees, the algorithm provides significantly shorter solutions. It solves real world instances with 783\,352 terminals within 126 seconds, proving its practical applicability. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2560519.2560529 | ISPD |
Keywords | Field | DocType |
central task,rectilinear steiner tree,obstacle structure,traversing obstacle,repeater tree topology,length restriction,chip design,2-approximation algorithm,fast algorithm,k log k,obstacle corner point,obstacle-avoiding tree,minimum rectilinear steiner tree,steiner tree | Steiner tree problem,Obstacle,Discrete mathematics,Mathematical optimization,Combinatorics,Algorithm,Rectilinear Steiner tree,Network topology,Integrated circuit design,Connected component,Repeater,Mathematics,Bounded function | Conference |
Citations | PageRank | References |
1 | 0.36 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stephan Held | 1 | 102 | 10.78 |
| Sophie Theresa Spirkl | 2 | 8 | 7.36 |