DocumentCode
2356900
Title
Finding separator cuts in planar graphs within twice the optimal
Author
Garg, Naveen ; Saran, Hutur ; Vazirani, Vijay V.
Author_Institution
Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., New Delhi, India
fYear
1994
fDate
20-22 Nov 1994
Firstpage
14
Lastpage
23
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⩽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
Keywords
computational geometry; graph theory; VLSI design; binary vertex weights; factor 2 approximation algorithm; minimum cost b-balanced cut; planar graphs; psuedo-approximation algorithm; separator cuts; vertex weights; Approximation algorithms; Circuits; Computer science; Cost function; Iterative algorithms; Particle separators; Partitioning algorithms; Very large scale integration;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
Conference_Location
Santa Fe, NM
Print_ISBN
0-8186-6580-7
Type
conf
DOI
10.1109/SFCS.1994.365709
Filename
365709
Link To Document