ND41 M INIMUM R ECTILINEAR G LOBAL R OUTING

     
• I NSTANCE : -array of gates, collection C of nets, i.e., 3-sets of gates.
• S OLUTION : Wires following rectilinear paths connecting the gates in each net.
• M EASURE : The largest number of wires in the same channel between two gates in the array.

• Good News: Admits a if [ 304 ].
• Comment: Approximable within if . In A PX 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.