A correct network flow model for escape routing

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

Abstract

Escape routing for packages and PCBs has been studied extensively in the past. Network flow is pervasively used to model this problem. However, none of the previous works correctly models the diagonal capacity, which is essential for 45? routing in most packages and PCBs. As a result, existing algorithms may either produce routing solutions that violate the diagonal capacity or fail to output a legal routing even though there exists one. In this paper, we propose a new network flow model that guarantees the correctness when diagonal capacity is taken into consideration. This model leads to the first optimal algorithm for escape routing. We also extend our model to handle missing pins.

Original languageEnglish (US)
Title of host publication2009 46th ACM/IEEE Design Automation Conference, DAC 2009
Pages332-335
Number of pages4
StatePublished - Nov 10 2009
Event2009 46th ACM/IEEE Design Automation Conference, DAC 2009 - San Francisco, CA, United States
Duration: Jul 26 2009Jul 31 2009

Publication series

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

Other

Other2009 46th ACM/IEEE Design Automation Conference, DAC 2009
CountryUnited States
CitySan Francisco, CA
Period7/26/097/31/09

Keywords

  • Diagonal capacity
  • Escape routing
  • Missing pin
  • Network flow
  • PCB routing
  • Package routing

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modeling and Simulation

Fingerprint Dive into the research topics of 'A correct network flow model for escape routing'. Together they form a unique fingerprint.

  • Cite this

    Tan, Y., & Wong, M. D. F. (2009). A correct network flow model for escape routing. In 2009 46th ACM/IEEE Design Automation Conference, DAC 2009 (pp. 332-335). [5227129] (Proceedings - Design Automation Conference).