Univeristy of Maryland College Park Computer Science Technical Report Series
CS-TR-2849 and UMIACS-TR-92-95
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.
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.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.