In this talk we focus on channel and switchbox routing problems.
From a graph-theoretical perspective, we are concerned with path and Steiner tree packing problems in grid graphs. This talk consists of two major parts. In the first part, we focus on complexity issues. From a graph-theoretical perspective, we are concerned with path and Steiner tree packing problems in grid graphs. Our main result of the complexity part is that the switchbox routing problem is NP-complete even if no net has more than three terminals. Hence, from the theoretical perspective, the switchbox routing problem is completely settled, since we entirely close the gap between the polynomially solvable 2-terminal case and the NP-complete 5-terminal case. We adopt our construction to prove the NP-completeness of the 4-terminal 3-sided switchbox routing and the 5-terminal channel routing problem.
The second part of this talk is dedicated to the development of routing algorithms. The main result of this part is a run-time optimal algorithm generating area-optimal layouts for the minimum total wire length problem for single-line routing. Up to this point, we only consider problems in the knock-knee model. For the Manhattan model, we develop an LP-based Monte Carlo epsilon-approximation algorithm for the minimum total wire length problem for single-line routing.
Copyright. All Rights Reserved.