Minimizing channel density by lateral shifting of components

D. S. Johnson, A. S. LaPaugh, R. Y. Pinter

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


We consider a channel layout model in which we are free to change the spacing, but not the ordering, of the components on the top and bottom of a routing channel. The goal is to minimize channel density. Let N be the total number of terminals on top and bottom components. The main previous approach to this problem used dynamic programming and restricted the potential locations for components and their terminals to grid points along a one-dimensional line, yielding running times polynomial in L, where L is the length of the grid. To use such an algorithm in an environment where high-precision placement is possible, however, one must have a very fine grid, with L growing as Ω(N2) or worse. Consequently, the running time could grow very large as a function of N. We prove a key combinatorial lemma that implies that the run time for a grid-free dynamic programming algorithm can be polynomially bounded. Based on this lemma, a naive O(N5) algorithm is derived. We then show how this can be sped up to O(N3) by computing appropriately defined auxiliary functions. For certain instances of the problem in which all components are roughly the same size and have roughly √N terminals, we can further reduce the running time to O(N2.5).

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
PublisherPubl by ACM
Number of pages10
ISBN (Print)0898713293
StatePublished - 1994
EventProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA
Duration: Jan 23 1994Jan 25 1994

Publication series

NameProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms


OtherProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms
CityArlington, VA, USA

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Minimizing channel density by lateral shifting of components'. Together they form a unique fingerprint.

Cite this