Article
Minimizing Channel Density with Movable Terminals
Algorithmica
Document Type
Article
Publication Date
2-1-1997
Pages
89-99
Publisher Name
Springer-Verlag
Disciplines
Abstract
We give algorithms to minimize density for VLSI channel routing problems 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, we improve previous results for running time and space by a factor of L/\lgn and L, respectively, where L is the channel length, and n is the number of terminals.
Identifier
1432-0541
Creative Commons License
Creative Commons Attribution-Noncommercial-No Derivative Works 3.0
Copyright Statement
© Springer-Verlag New York Inc. 1997
Citation Information
Ronald I. Greenberg and Jau-Der Shih. "Minimizing Channel Density with Movable Terminals" Algorithmica Vol. 17 Iss. 2 (1997) Available at: http://works.bepress.com/ronald-greenberg/34/
Author Posting. © Springer-Verlag New York Inc. 1997. This is the author's version of the work. It is posted here by permission of Springer-Verlag for personal use, not for redistribution. The definitive version was published in Greenberg, R.I. & Shih, J.D. Algorithmica (1997) 17: 89. https://doi.org/10.1007/BF02522820.
This is a revised version of the conference paper that can be found at http://ecommons.luc.edu/cs_facpubs/101 (along with presentation slides).