SINGLE-ROW ROUTING PROBLEM WITH ALTERNATIVE TERMINALS

Abstract

The present article concentrates on the dogleg-free Manhattan model where horizontal and vertical wire segments are positioned on different sides of the board and each net (wire) has at most one horizontal segment. Gallai's classical result on interval packing can be applied in VLS1 routing to find, in linear time, a minimum-width dogleg-free routing in the Manhattan model, provided that all the terminals are on one side of a rectangular (single-row routing). We deal with the generalization of this routing problem when we have the possibility to select another terminal from a corresponding set instead of a terminal to be connected. It will be shown that in this case there is no hope to find a polynomial algorithm because this problem is NP-complete. The results on dogleg-free Manhattan routing can be connected with other application areas related to colouring of interval graphs. In this paper the alternative interval placement problem will be defined. We show that this problem is NP-complete. This implies the NP-completeness of the single-row routing problem with alternative terminals.