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

Endre Boros, András Recski, Tibor Szkaliczki, Ferenc Wettl

Research output: Contribution to journalArticle

1 Scopus citations

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 languageEnglish (US)
Pages (from-to)403-413
Number of pages11
JournalComputers and Artificial Intelligence
Volume18
Issue number4
StatePublished - 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