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 Citation (Scopus)

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

Fingerprint

Computational complexity
Polynomials

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Complexity
  • Manhattan model
  • Polynomial algorithm
  • Routing
  • VLSI

Cite this

Boros, Endre ; Recski, András ; Szkaliczki, Tibor ; Wettl, Ferenc. / Polynomial time Manhattan routing without doglegs - A generalization of Gallai's algorithm. In: Computers and Artificial Intelligence. 1999 ; Vol. 18, No. 4. pp. 403-413.
@article{e4b97c65efff47d3b43cc429f7d3a66c,
title = "Polynomial time Manhattan routing without doglegs - A generalization of Gallai's algorithm",
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.",
keywords = "Complexity, Manhattan model, Polynomial algorithm, Routing, VLSI",
author = "Endre Boros and Andr{\'a}s Recski and Tibor Szkaliczki and Ferenc Wettl",
year = "1999",
month = "12",
day = "1",
language = "English (US)",
volume = "18",
pages = "403--413",
journal = "Computing and Informatics",
issn = "1335-9150",
publisher = "Slovak Academy of Sciences",
number = "4",

}

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

In: Computers and Artificial Intelligence, Vol. 18, No. 4, 01.12.1999, p. 403-413.

Research output: Contribution to journalArticle

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 -