Masters Theses

Date of Award


Degree Type


Degree Name

Master of Science


Computer Science

Major Professor

D. P. Mehta

Committee Members

Bruce Whitehead, Bruce Bomar


The greedy and left edge algorithms, as applied to local routing in VLSI CAD, were modified to decrease crosstalk between neighboring wires. The modifications on the algorithms use spacing, and segregation to improve the routing of wires in a channel. The modified greedy and left edge algorithms use a grid, but the minimum distance between two wires can be varied depending on the crosstalk between them. Crosstalk information must be obtained separately and is part of the required set of inputs to the algorithms. The improved algorithms route all the channel problems tested in less tracks than the original algorithms, if crosstalk constraints exist, and in the same number of tracks, if no crosstalk constraints exist.

Files over 3MB may be slow to open. For best results, right-click and select "save as..."