Near-optimal n-layer channel routing

R. J. Enbody, H. C. Du

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations


In this paper we present two n-layer channel routing algorithms that guarantee successful routing of the channel for n greater than three. The first is linear and optimal given a VHV...HV assignment of layers. The second, using an HVH...VH layer assignment, is quasilinear and performs optimally on examples from the literature. Except in pathological cases, we expect the latter router to perform within one row of optimal. For comparison with published examples we implemented the second router in five and three layers. The five-layer implementation routed all examples optimally while the three-layer implementation routed the examples with the same or fewer rows than the published examples. With its n-layer capability this channel router will allow channel routing to be used when more than three layers are available. This router can also be used to evaluate the utility of additional layers.

Original languageEnglish (US)
Title of host publicationProceedings of the 23rd ACM/IEEE Design Automation Conference, DAC 1986
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages7
ISBN (Print)0818607025
StatePublished - Jul 2 1986
Event23rd ACM/IEEE Design Automation Conference, DAC 1986 - Las Vegas, United States
Duration: Jun 29 1986Jul 2 1986

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X


Other23rd ACM/IEEE Design Automation Conference, DAC 1986
Country/TerritoryUnited States
CityLas Vegas

Bibliographical note

Funding Information:
in part by ‘NSF grant DCR-

Publisher Copyright:
© 1986 IEEE.


Dive into the research topics of 'Near-optimal n-layer channel routing'. Together they form a unique fingerprint.

Cite this