### Abstract

Gallai's classical result on interval packing can be applied in VLSI routing to find, in linear time, a minimum-width dogleg-free routing in the Manhattan model, provided that all the terminals are on one side of a rectangular [1]. Should the terminals appear on two opposite sides of the rectangular, the corresponding "channel routing problem" is NP-complete [2,3]. We generalize Gallai's result for the case if the terminals appear on two adjacent sides of the rectangular.

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

Pages (from-to) | 403-413 |

Number of pages | 11 |

Journal | Computers and Artificial Intelligence |

Volume | 18 |

Issue number | 4 |

State | Published - Dec 1 1999 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

### Keywords

- Complexity
- Manhattan model
- Polynomial algorithm
- Routing
- VLSI

## Fingerprint Dive into the research topics of 'Polynomial time Manhattan routing without doglegs - A generalization of Gallai's algorithm'. Together they form a unique fingerprint.

## Cite this

Boros, E., Recski, A., Szkaliczki, T., & Wettl, F. (1999). Polynomial time Manhattan routing without doglegs - A generalization of Gallai's algorithm.

*Computers and Artificial Intelligence*,*18*(4), 403-413.