Document Type

Presentation

Publication Date

2-25-1992

Publication Title

Univeristy of Maryland College Park Computer Science Technical Report Series

Issue

CS-TR-2849 and UMIACS-TR-92-95

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 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.

Download

Share

COinS