×

Routing with minimum wire length in the dogleg-free manhattan model is \(\mathcal NP\)-complete. (English) Zbl 0937.68055

Summary: 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. While the minimum width can be found in linear time in the single row routing, apparently there was no efficient algorithm to find the minimum wire length. We show that there is no hope to find such an algorithm because this problem is \({\mathcal NP}\)-complete even if each net has only two terminals. The results on dogleg-free Manhattan routing can be connected with other application areas related to interval graphs. In this paper we define the minimum value interval placement problem. There is given a set of weighted intervals and \(w\) rows and the intervals have to be placed without overlapping into rows so that the sum of the interval values, which is the value of a function of the weight and the row number assigned to the interval, is minimum. We show that this problem is \({\mathcal NP}\)-complete. This implies the \({\mathcal NP}\)-completeness of other problems including the minimum wire length routing and the sum coloring on interval graphs.

MSC:

68Q25 Analysis of algorithms and problem complexity
68W35 Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)
PDFBibTeX XMLCite
Full Text: DOI