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

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

Fingerprint Dive into the research topics of 'An optimal algorithm for finding disjoint rectangles and its application to PCB routing'. Together they form a unique fingerprint.

  • 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