An optimal algorithm for finding disjoint rectangles and its application to PCB routing

Hui Kong, Qiang Ma, Tan Yan, Martin D F Wong

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

Abstract

The maximum disjoint subset (MDS) of rectangles is a subset of non-overlapping rectangles with the maximum total weight. The problem of finding the MDS of general rectangles has been proven to be NP-complete in [6]. In this paper, we focus on the problem of finding the MDS of boundary rectangles, which is an open problem and is closely related to some difficult problems in PCB routing. We propose a polynomial time algorithm to optimally solve the MDS problem of boundary rectangles. Then we show that this algorithm can be applied to find the optimal solution of the bus escape routing problem.

Original languageEnglish (US)
Title of host publicationProceedings of the 47th Design Automation Conference, DAC '10
Pages212-217
Number of pages6
DOIs
StatePublished - Sep 7 2010
Event47th Design Automation Conference, DAC '10 - Anaheim, CA, United States
Duration: Jun 13 2010Jun 18 2010

Publication series

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

Other

Other47th Design Automation Conference, DAC '10
CountryUnited States
CityAnaheim, CA
Period6/13/106/18/10

Fingerprint

Polychlorinated biphenyls
Optimal Algorithm
Rectangle
Disjoint
Routing
Subset
Polynomials
Routing Problem
Polynomial-time Algorithm
Open Problems
NP-complete problem
Optimal Solution

Keywords

  • Escape routing
  • Maximum independent subset
  • PCB routing

ASJC Scopus subject areas

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

Cite this

Kong, H., Ma, Q., Yan, T., & Wong, M. D. F. (2010). An optimal algorithm for finding disjoint rectangles and its application to PCB routing. In Proceedings of the 47th Design Automation Conference, DAC '10 (pp. 212-217). (Proceedings - Design Automation Conference). https://doi.org/10.1145/1837274.1837326

An optimal algorithm for finding disjoint rectangles and its application to PCB routing. / Kong, Hui; Ma, Qiang; Yan, Tan; Wong, Martin D F.

Proceedings of the 47th Design Automation Conference, DAC '10. 2010. p. 212-217 (Proceedings - Design Automation Conference).

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

Kong, H, Ma, Q, Yan, T & Wong, MDF 2010, An optimal algorithm for finding disjoint rectangles and its application to PCB routing. in Proceedings of the 47th Design Automation Conference, DAC '10. Proceedings - Design Automation Conference, pp. 212-217, 47th Design Automation Conference, DAC '10, Anaheim, CA, United States, 6/13/10. https://doi.org/10.1145/1837274.1837326
Kong H, Ma Q, Yan T, Wong MDF. An optimal algorithm for finding disjoint rectangles and its application to PCB routing. In Proceedings of the 47th Design Automation Conference, DAC '10. 2010. p. 212-217. (Proceedings - Design Automation Conference). https://doi.org/10.1145/1837274.1837326
Kong, Hui ; Ma, Qiang ; Yan, Tan ; Wong, Martin D F. / An optimal algorithm for finding disjoint rectangles and its application to PCB routing. Proceedings of the 47th Design Automation Conference, DAC '10. 2010. pp. 212-217 (Proceedings - Design Automation Conference).
@inproceedings{156d84506c654ea186eae2bce258b626,
title = "An optimal algorithm for finding disjoint rectangles and its application to PCB routing",
abstract = "The maximum disjoint subset (MDS) of rectangles is a subset of non-overlapping rectangles with the maximum total weight. The problem of finding the MDS of general rectangles has been proven to be NP-complete in [6]. In this paper, we focus on the problem of finding the MDS of boundary rectangles, which is an open problem and is closely related to some difficult problems in PCB routing. We propose a polynomial time algorithm to optimally solve the MDS problem of boundary rectangles. Then we show that this algorithm can be applied to find the optimal solution of the bus escape routing problem.",
keywords = "Escape routing, Maximum independent subset, PCB routing",
author = "Hui Kong and Qiang Ma and Tan Yan and Wong, {Martin D F}",
year = "2010",
month = "9",
day = "7",
doi = "10.1145/1837274.1837326",
language = "English (US)",
isbn = "9781450300025",
series = "Proceedings - Design Automation Conference",
pages = "212--217",
booktitle = "Proceedings of the 47th Design Automation Conference, DAC '10",

}

TY - GEN

T1 - An optimal algorithm for finding disjoint rectangles and its application to PCB routing

AU - Kong, Hui

AU - Ma, Qiang

AU - Yan, Tan

AU - Wong, Martin D F

PY - 2010/9/7

Y1 - 2010/9/7

N2 - The maximum disjoint subset (MDS) of rectangles is a subset of non-overlapping rectangles with the maximum total weight. The problem of finding the MDS of general rectangles has been proven to be NP-complete in [6]. In this paper, we focus on the problem of finding the MDS of boundary rectangles, which is an open problem and is closely related to some difficult problems in PCB routing. We propose a polynomial time algorithm to optimally solve the MDS problem of boundary rectangles. Then we show that this algorithm can be applied to find the optimal solution of the bus escape routing problem.

AB - The maximum disjoint subset (MDS) of rectangles is a subset of non-overlapping rectangles with the maximum total weight. The problem of finding the MDS of general rectangles has been proven to be NP-complete in [6]. In this paper, we focus on the problem of finding the MDS of boundary rectangles, which is an open problem and is closely related to some difficult problems in PCB routing. We propose a polynomial time algorithm to optimally solve the MDS problem of boundary rectangles. Then we show that this algorithm can be applied to find the optimal solution of the bus escape routing problem.

KW - Escape routing

KW - Maximum independent subset

KW - PCB routing

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

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

U2 - 10.1145/1837274.1837326

DO - 10.1145/1837274.1837326

M3 - Conference contribution

AN - SCOPUS:77956210463

SN - 9781450300025

T3 - Proceedings - Design Automation Conference

SP - 212

EP - 217

BT - Proceedings of the 47th Design Automation Conference, DAC '10

ER -