Document Type

Conference Proceeding

Publication Date


Publication Title

Third Great Lakes Symposium on VLSI (GLSV '93)

Publisher Name

IEEE Computer Society


We give algorithms to minimize density for channels with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, previous results for running time and space are improved by a factor of L/lg n and L , respectively, where L is the channel length and n is the number of terminals.


Author Posting. © IEEE, 1993. This article is posted here by permission of IEEE for personal use, not for redistribution. The article was published in VLSI, 1993. 'Design Automation of High Performance VLSI Systems', Proceedings., Third Great Lakes Symposium on VLSI (GLSV '93),

A revised version can be found at

Creative Commons License

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.