A correct network flow model for escape routing

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

54 Citations (Scopus)

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
Title of host publication46th ACM/IEEE Design Automation Conference - Proceedings 2009
PublisherAssociation for Computing Machinery (ACM)
Pages332-335
Number of pages4
ISBN (Print)9781605584973
DOIs
Publication statusPublished - 29 Jul 2009
Event46th ACM/IEEE Design Automation Conference, DAC 2009 - San Francisco, United States
Duration: 26 Jul 200931 Jul 2009
https://www.dac.com/About/Conference-Archive/46th-DAC-2009 (Conference website)
https://www.dac.com/portals/0/documents/archive/2009/46DAC_Final_Prgm.pdf (Conference programme )
https://dl.acm.org/doi/proceedings/10.1145/1629911 (Conference proceedings)
https://ieeexplore.ieee.org/xpl/conhome/5209519/proceeding

Publication series

NameACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)0738-100X

Conference

Conference46th ACM/IEEE Design Automation Conference, DAC 2009
Country/TerritoryUnited States
CitySan Francisco
Period26/07/0931/07/09
Internet address

Scopus Subject Areas

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

User-Defined Keywords

  • Escape routing
  • diagonal capacity
  • missing pin
  • network flow
  • package routing
  • PCB routing

Fingerprint

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

Cite this