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 - 2009
Event2009 46th ACM/IEEE Design Automation Conference, DAC 2009 - San Francisco, CA, United States
Duration: Jul 26 2009Jul 31 2009

Other

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

Fingerprint

Network Flow
Routing
Polychlorinated biphenyls
Model
Violate
Optimal Algorithm
Correctness
Output

Keywords

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

ASJC Scopus subject areas

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

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]

A correct network flow model for escape routing. / Tan, Yan; Wong, Martin D F.

2009 46th ACM/IEEE Design Automation Conference, DAC 2009. 2009. p. 332-335 5227129.

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

Tan, Y & Wong, MDF 2009, A correct network flow model for escape routing. in 2009 46th ACM/IEEE Design Automation Conference, DAC 2009., 5227129, pp. 332-335, 2009 46th ACM/IEEE Design Automation Conference, DAC 2009, San Francisco, CA, United States, 7/26/09.
Tan Y, Wong MDF. A correct network flow model for escape routing. In 2009 46th ACM/IEEE Design Automation Conference, DAC 2009. 2009. p. 332-335. 5227129
Tan, Yan ; Wong, Martin D F. / A correct network flow model for escape routing. 2009 46th ACM/IEEE Design Automation Conference, DAC 2009. 2009. pp. 332-335
@inproceedings{1101628e5b5c4139b6cd62d044589bd0,
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 = "Diagonal capacity, Escape routing, Missing pin, Network flow, Package routing, PCB routing",
author = "Yan Tan and Wong, {Martin D F}",
year = "2009",
language = "English (US)",
isbn = "9781605584973",
pages = "332--335",
booktitle = "2009 46th ACM/IEEE Design Automation Conference, DAC 2009",

}

TY - GEN

T1 - A correct network flow model for escape routing

AU - Tan, Yan

AU - Wong, Martin D F

PY - 2009

Y1 - 2009

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 - Diagonal capacity

KW - Escape routing

KW - Missing pin

KW - Network flow

KW - Package routing

KW - PCB routing

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

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

M3 - Conference contribution

AN - SCOPUS:70350733799

SN - 9781605584973

SP - 332

EP - 335

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

ER -