### 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 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

### Keywords

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

### Cite this

*Computers and Artificial Intelligence*,

*18*(4), 403-413.

}

*Computers and Artificial Intelligence*, vol. 18, no. 4, pp. 403-413.

**Polynomial time Manhattan routing without doglegs - A generalization of Gallai's algorithm.** / Boros, Endre; Recski, András; Szkaliczki, Tibor; Wettl, Ferenc.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Polynomial time Manhattan routing without doglegs - A generalization of Gallai's algorithm

AU - Boros, Endre

AU - Recski, András

AU - Szkaliczki, Tibor

AU - Wettl, Ferenc

PY - 1999/12/1

Y1 - 1999/12/1

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

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

KW - Complexity

KW - Manhattan model

KW - Polynomial algorithm

KW - Routing

KW - VLSI

UR - http://www.scopus.com/inward/record.url?scp=33748607206&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748607206&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:33748607206

VL - 18

SP - 403

EP - 413

JO - Computing and Informatics

JF - Computing and Informatics

SN - 1335-9150

IS - 4

ER -