Title :
On multiterminal single bend wirability
Author_Institution :
Dept. of Electr. Eng., Nat. Taiwan Univ., Taipei, Taiwan
fDate :
6/1/1994 12:00:00 AM
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)
Keywords :
VLSI; circuit layout CAD; computational complexity; multiterminal networks; network routing; NP-complete problem; fixed length wires; generalized model; multiterminal nets; polynomial time; single bend wirability; Algorithm design and analysis; Approximation algorithms; Computational complexity; Frequency; Heuristic algorithms; Joining processes; Polynomials; Routing; Very large scale integration; Wire;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
