On multiterminal single bend wirability.
Journal
IEEE Trans. on CAD of Integrated Circuits and Systems
Journal Volume
13
Journal Issue
6
Pages
822-826
Date Issued
1994
Author(s)
Abstract
In a paper by Raghavan, Cohoon, and Sahni (see J. Algorithms, vol. 7, p. 232-57, 1986), the single layer single bend wirability problem has been shown to be solvable in polynomial time for two-terminal nets. In this paper, we investigate the problem for a slightly generalized model in which nets are allowed to have two or more terminals. We show that for multiterminal nets, the single bend wirability problem becomes NP-complete, even when all wires are 'short' (i.e. of fixed length).>
Type
journal article