ROUTING WITH MINIMUM WIRE LENGTH IN THE MANHATTAN MODEL IS NP-COMPLETE
Abstract
The present paper concentrates on one of the most common routing models, on the Manhattan model where horizontal and vertical wire segments are positioned on different sides of the board. 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 showed before that this problem is NP-complete in the dogleg-free case but the complexity of the problem was still unknown in the general case. In this paper we modify the construction applied in the former proof in order to show the NP-completeness of routing with minimum wire length in the Manhattan model without any restrictions.
Keywords:
single row routing, VLSI, NP-complete problems, minimum lengthHow to Cite
Szkaliczki, T. “ROUTING WITH MINIMUM WIRE LENGTH IN THE MANHATTAN MODEL IS NP-COMPLETE”, Periodica Polytechnica Electrical Engineering, 46(3-4), pp. 175–194, 2002.
Issue
Section
Articles