In this thesis we consider the global routing problem, which arises as one of the major subproblems in the physical design step in VLSI design. In global routing, we are given a three-dimensional grid graph G with edge ...

In this thesis we consider detailed routing, an important step in the design of integrated circuits. On large instances detailed routing requires packing millions of node-disjoint Steiner trees into a graph with hundreds ......