Garg, N. ; Saran, H. ; Vazirani, V. V. (1994) Finding separator cuts in planar graphs within twice the optimal In: 35th Annual Symposium on Foundations of Computer Science, November 20-22, 1994, Santa Fe, NM, USA.
Full text not available from this repository.
Official URL: http://ieeexplore.ieee.org/document/365709/
Abstract
Building on the works of S.B. Rao (1987, 1992) and J.K. Park and C.A. Phillips (1993), we present a factor 2 approximation algorithm for the problem of finding a minimum cost b-balanced cut in planar graphs, for b/spl les/1/3, if the vertex weights are given in unary (using scaling, a psuedo-approximation algorithm is also presented for the case of binary vertex weights). This problem is of considerable practical significance, especially in VLSI design.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Source: | Copyright of this article belongs to Institute of Electrical and Electronics Engineers. |
| Keywords: | Particle Separators; Approximation Algorithms; Very Large Scale Integration; Iterative Algorithms; Cost Function; Circuits; Partitioning Algorithms; Computer Science |
| ID Code: | 101330 |
| Deposited On: | 31 Jan 2018 09:34 |
| Last Modified: | 31 Jan 2018 09:34 |
Repository Staff Only: item control page
