ROUTING WITH MINIMUM WIRE LENGTH IN THE MANHATTAN MODEL IS NP-COMPLETE

Authors

  • Tibor Szkaliczki

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 length

How 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