Document Type

Article

Publication Date

2-1997

Publication Title

Algorithmica

Volume

17

Issue

2

Pages

89-99

Publisher Name

Springer-Verlag

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

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.

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).

Creative Commons License

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

Download

Share

COinS