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.
Greenberg, Ronald I. and Shih, Jau-Der. Minimizing Channel Density with Movable Terminals. Algorithmica, 17, 2: 89-99, 1997. Retrieved from Loyola eCommons, Computer Science: Faculty Publications and Other Works, http://dx.doi.org/10.1007/BF02522820
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
© Springer-Verlag New York Inc. 1997
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).