Next: MINIMUM TRAVELING REPAIRMAN Up: Routing Problems Previous: SHORTEST WEIGHT-CONSTRAINED PATH Index

### MINIMUM RECTILINEAR GLOBAL ROUTING

- INSTANCE: m x n-array of gates, collection C of nets, i.e., 3-sets of gates.

- SOLUTION: Wires following rectilinear paths connecting the gates in each net.

- MEASURE: The largest number of wires in the same channel between two gates in the array.

- Good News: Admits a if [392].

- Comment: Approximable within if . In APX if . The approximation algorithm will work also for nets with more than three gates, but the running time is exponential in the number of terminals.