@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",
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",
note = "47th Design Automation Conference, DAC '10 ; Conference date: 13-06-2010 Through 18-06-2010",
}