A correct network flow model for escape routing

Yan Tan; Martin D. F. Wong

doi:10.1145/1629911.1630001

A correct network flow model for escape routing

Yan Tan, Martin D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

58 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 language	English
Title of host publication	46th ACM/IEEE Design Automation Conference - Proceedings 2009
Publisher	Association for Computing Machinery (ACM)
Pages	332-335
Number of pages	4
ISBN (Print)	9781605584973
DOIs	https://doi.org/10.1145/1629911.1630001
Publication status	Published - 29 Jul 2009
Event	46th ACM/IEEE Design Automation Conference, DAC 2009 - San Francisco, United States Duration: 26 Jul 2009 → 31 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

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

Conference

Conference	46th ACM/IEEE Design Automation Conference, DAC 2009
Country/Territory	United States
City	San Francisco
Period	26/07/09 → 31/07/09
Internet address	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

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

Access to Document

10.1145/1629911.1630001

Cite this

@inproceedings{641e9496626c4799a280af9b4f36bcd7,

title = "A correct network flow model for escape routing",

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.",

keywords = "Escape routing, diagonal capacity, missing pin, network flow, package routing, PCB routing",

author = "Yan Tan and Wong, {Martin D. F.}",

note = "Funding information: This work was partially supported by the National Science Foundation under grant CCF-0701821 and a grant from the Fujitsu Laboratories.; 46th ACM/IEEE Design Automation Conference, DAC 2009 ; Conference date: 26-07-2009 Through 31-07-2009",

year = "2009",

month = jul,

day = "29",

doi = "10.1145/1629911.1630001",

language = "English",

isbn = "9781605584973",

series = "ACM/IEEE Design Automation Conference - Proceedings",

publisher = "Association for Computing Machinery (ACM)",

pages = "332--335",

booktitle = "46th ACM/IEEE Design Automation Conference - Proceedings 2009",

address = "United States",

url = "https://www.dac.com/About/Conference-Archive/46th-DAC-2009, https://www.dac.com/portals/0/documents/archive/2009/46DAC_Final_Prgm.pdf, https://dl.acm.org/doi/proceedings/10.1145/1629911, https://ieeexplore.ieee.org/xpl/conhome/5209519/proceeding",

}

Tan, Y & Wong, MDF 2009, A correct network flow model for escape routing. in 46th ACM/IEEE Design Automation Conference - Proceedings 2009. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 332-335, 46th ACM/IEEE Design Automation Conference, DAC 2009, San Francisco, California, United States, 26/07/09. https://doi.org/10.1145/1629911.1630001

TY - GEN

T1 - A correct network flow model for escape routing

AU - Tan, Yan

AU - Wong, Martin D. F.

N1 - Funding information: This work was partially supported by the National Science Foundation under grant CCF-0701821 and a grant from the Fujitsu Laboratories.

PY - 2009/7/29

Y1 - 2009/7/29

N2 - 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.

AB - 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.

KW - Escape routing

KW - diagonal capacity

KW - missing pin

KW - network flow

KW - package routing

KW - PCB routing

UR - https://dl.acm.org/doi/10.1145/1629911.1630001

UR - https://ieeexplore.ieee.org/document/5227129

UR - http://www.scopus.com/inward/record.url?scp=70350733799&partnerID=8YFLogxK

U2 - 10.1145/1629911.1630001

DO - 10.1145/1629911.1630001

M3 - Conference proceeding

AN - SCOPUS:70350733799

SN - 9781605584973

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 332

EP - 335

BT - 46th ACM/IEEE Design Automation Conference - Proceedings 2009

PB - Association for Computing Machinery (ACM)

T2 - 46th ACM/IEEE Design Automation Conference, DAC 2009

Y2 - 26 July 2009 through 31 July 2009

ER -

A correct network flow model for escape routing

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this