Efficient maze-running and line-search algorithms for VLSI layout

A new construct called the connection graph G/sup 4/, is proposed. An efficient geometric algorithm for constructing G/sup 4/ 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 t...

Full description

Saved in:
Bibliographic Details
Main Authors: Zheng, S.-Q., Lim, J.S., Iyengar, S.S.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Circuits
Computer science
Design automation
Joining processes
Power system modeling
Routing
Tree graphs
Very large scale integration
Wires
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A new construct called the connection graph G/sup 4/, is proposed. An efficient geometric algorithm for constructing G/sup 4/ 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 G/sup 4/. Several example maze-running and line-search algorithms based on G/sup 4/ are given to demonstrate the power of G/sup 4/ in designing good sequential VLSI routing algorithms.< >
DOI:10.1109/SECON.1993.465749