Title :
Modified interval line representation and its applications to planar routing problems
Author :
Saxena, Sanjeev ; Prasad, V.C. ; Bhatt, P.C.P.
Author_Institution :
Comput. Sci. Eng., Indian Inst. of Technol., Kanpur, India
Abstract :
A modified interval line representation is proposed. This representation makes it possible to speed up some heuristics and algorithms for planar routing problems. This technique is illustrated by speeding up the heuristic proposed by Tsukiyama and Kuh for the double row routing problem. The heuristic suggested by Tsukiyama and Kuh for double row routing problem, can be implemented in O(n2rlg r) time algorithm, whereas the implementation suggested by Tsukiyama and Kuh requires O(n3r) time. It is also shown that the heuristic can be implemented in parallel in O(lg2n+lg r) time using O(N 4+n2r) processors on the concurrent read exclusive write (CREW) model
Keywords :
VLSI; circuit layout CAD; computational geometry; concurrent read exclusive write; double row routing; heuristics; modified interval line representation; parallel implementation; planar routing problems; Computational geometry; Computer aided software engineering; Conductors; Explosives; Heuristic algorithms; Joining processes; Routing; Very large scale integration; Wire;
Conference_Titel :
VLSI Design, 1991. Proceedings., Fourth CSI/IEEE International Symposium on
Conference_Location :
New Delhi
Print_ISBN :
0-8186-2125-7
DOI :
10.1109/ISVD.1991.185112
