### Abstract

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 Ω(N^{2}) 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(N^{5}) algorithm is derived. We then show how this can be sped up to O(N^{3}) 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(N^{2.5}).

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms |

Publisher | Publ by ACM |

Pages | 122-131 |

Number of pages | 10 |

ISBN (Print) | 0898713293 |

State | Published - Jan 1 1994 |

Externally published | Yes |

Event | Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA Duration: Jan 23 1994 → Jan 25 1994 |

### Publication series

Name | Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms |
---|---|

City | Arlington, VA, USA |

Period | 1/23/94 → 1/25/94 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

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

## Cite this

*Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms*(pp. 122-131). (Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms). Publ by ACM.