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 proceedingpeer-review

27 Citations (Scopus)

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
Title of host publication47th ACM/IEEE Design Automation Conference - Proceedings 2010
PublisherAssociation for Computing Machinery (ACM)
Pages212-217
Number of pages6
ISBN (Electronic)9781450300025
DOIs
Publication statusPublished - 15 Jun 2010
Event47th ACM/IEEE Design Automation Conference, DAC 2010 - Anaheim, United States
Duration: 13 Jun 201018 Jun 2010
https://www.dac.com/About/Conference-Archive/47th-DAC-2010 (Conference website)
https://www.dac.com/Portals/0/Documents/Archive/2010/47th_DAC_FP_book_front.pdf (Conference programme)
https://dl.acm.org/doi/proceedings/10.1145/1837274 (Conference proceedings)
https://ieeexplore.ieee.org/xpl/conhome/5510861/proceeding (Conference proceedings)

Publication series

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

Conference

Conference47th ACM/IEEE Design Automation Conference, DAC 2010
Country/TerritoryUnited States
CityAnaheim
Period13/06/1018/06/10
Internet address

Scopus Subject Areas

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

User-Defined Keywords

  • Escape routing
  • PCB routing
  • Maximum independent subset

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