Document Type

Article

Publication Date

2-1997

Publication Title

Algorithmica

Volume

17

Issue

2

Pages

89-99

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.

Comments

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.

Creative Commons License

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

Share

COinS