Skip to main content
Presentation
Finding a Maximum-Density Planar Subset of a Set of Nets in a Channel
Univeristy of Maryland College Park Computer Science Technical Report Series
  • Ronald I. Greenberg
  • Jau-Der Shih
Document Type
Presentation
Publication Date
2-25-1992
Abstract

We present efficient algorithms to find a maximum-density planar subset of n 2-pin nets in a channel. The simplest approach is to make repeated usage of Supowit's dynamic programming algorithm for finding a maximum-size planar subset, which leads to O(n^3) time to find a maximum-density planar subset. But we also provide an algorithm whose running time is dependent on other problem parameters and is often more efficient. A simple bound on the running time of this algorithm is O(nlgn+n(t+1)w), where t is the number of two-sided nets, and w is the number of nets in the output. Though the worst-case running time is still O(n^3), this algorithm achieves better results when either t or w is of modest magnitude. In the very special case when there are no two-sided nets, the bound stated above becomes O(nlgn+nw); this bound can also be achieved in the case of no single-sided nets. In addition, the bounds stated so far can be strengthened by incorporating into the running time the number of edges in certain interval overlap and interval containment graphs.

Creative Commons License
Creative Commons Attribution-Noncommercial-No Derivative Works 3.0
Citation Information
Ronald I. Greenberg and Jau-Der Shih. Finding a maximum-density planar subset of a set of nets in a channel. University of Maryland Institute for Advanced Computer Studies Technical Report UMIACS-TR-92-95 and Computer Science Technical Report CS-TR-2849, February 1992.