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

Hui Kong; Qiang Ma; Tan Yan; Martin D. F. Wong

doi:10.1145/1837274.1837326

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

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

Office of the Provost

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

29 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 language	English
Title of host publication	47th ACM/IEEE Design Automation Conference - Proceedings 2010
Publisher	Association for Computing Machinery (ACM)
Pages	212-217
Number of pages	6
ISBN (Electronic)	9781450300025
DOIs	https://doi.org/10.1145/1837274.1837326
Publication status	Published - 15 Jun 2010
Event	47th ACM/IEEE Design Automation Conference, DAC 2010 - Anaheim, United States Duration: 13 Jun 2010 → 18 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

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

Conference

Conference	47th ACM/IEEE Design Automation Conference, DAC 2010
Country/Territory	United States
City	Anaheim
Period	13/06/10 → 18/06/10
Internet address	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)

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

Access to Document

10.1145/1837274.1837326

Cite this

@inproceedings{34f7b48fc05d45d2a8ccf521a27acec1,

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, PCB routing, Maximum independent subset",

author = "Hui Kong and Qiang Ma and Tan Yan and Wong, {Martin D. F.}",

note = "Funding information: This work was supported by the National Science Foundation under grant CCF-0701821.; 47th ACM/IEEE Design Automation Conference, DAC 2010 ; Conference date: 13-06-2010 Through 18-06-2010",

year = "2010",

month = jun,

day = "15",

doi = "10.1145/1837274.1837326",

language = "English",

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

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

pages = "212--217",

booktitle = "47th ACM/IEEE Design Automation Conference - Proceedings 2010",

address = "United States",

url = "https://www.dac.com/About/Conference-Archive/47th-DAC-2010, https://www.dac.com/Portals/0/Documents/Archive/2010/47th_DAC_FP_book_front.pdf, https://dl.acm.org/doi/proceedings/10.1145/1837274, https://ieeexplore.ieee.org/xpl/conhome/5510861/proceeding",

}

Kong, H, Ma, Q, Yan, T & Wong, MDF 2010, An optimal algorithm for finding disjoint rectangles and its application to PCB routing. in 47th ACM/IEEE Design Automation Conference - Proceedings 2010. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 212-217, 47th ACM/IEEE Design Automation Conference, DAC 2010, Anaheim, California, United States, 13/06/10. 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 et al.
47th ACM/IEEE Design Automation Conference - Proceedings 2010. Association for Computing Machinery (ACM), 2010. p. 212-217 (ACM/IEEE Design Automation Conference - Proceedings).

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

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.

N1 - Funding information: This work was supported by the National Science Foundation under grant CCF-0701821.

PY - 2010/6/15

Y1 - 2010/6/15

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 - PCB routing

KW - Maximum independent subset

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

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

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

U2 - 10.1145/1837274.1837326

DO - 10.1145/1837274.1837326

M3 - Conference proceeding

AN - SCOPUS:77956210463

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 212

EP - 217

BT - 47th ACM/IEEE Design Automation Conference - Proceedings 2010

PB - Association for Computing Machinery (ACM)

T2 - 47th ACM/IEEE Design Automation Conference, DAC 2010

Y2 - 13 June 2010 through 18 June 2010

ER -

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

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this