Title :
Efficient maze-running and line-search algorithms for VLSI layout
Author :
Zheng, Si-Qing ; Lim, Joon Skil ; Iyengar, S Sitharama
Author_Institution :
Dept. of Comput. Sci., Louisiana State Univ., Baton Rouge, LA, USA
Firstpage :
0.791666666666667
Abstract :
A new construct called the connection graph G4, is proposed. An efficient geometric algorithm for constructing G4 is given. A framework is presented for designing a class of time and space efficient maze-running and line-search rectilinear shortest path and rectilinear minimum spanning tree algorithms based on G4. Several example maze-running and line-search algorithms based on G4 are given to demonstrate the power of G4 in designing good sequential VLSI routing algorithms
Keywords :
VLSI; circuit layout CAD; graph theory; network routing; G4; connection graph; geometric algorithm; line-search algorithms; maze-running algorithm; rectilinear minimum spanning tree algorithms; rectilinear shortest path algorithm; sequential VLSI routing algorithms; Algorithm design and analysis; Circuits; Computer science; Design automation; Joining processes; Power system modeling; Routing; Tree graphs; Very large scale integration; Wires;
Conference_Titel :
Southeastcon '93, Proceedings., IEEE
Conference_Location :
Charlotte, NC
Print_ISBN :
0-7803-1257-0
DOI :
10.1109/SECON.1993.465749
