Finding separator cuts in planar graphs within twice the optimal

Garg, Naveen ; Saran, Huzur ; Vazirani, Vijay V. (1999) Finding separator cuts in planar graphs within twice the optimal SIAM Journal on Computing, 29 (1). pp. 159-179. ISSN 0097-5397

Full text not available from this repository.

Official URL:

Related URL:


A factor 2 approximation algorithm for the problem of finding a minimum-cost b-balanced cut in planar graphs is presented, for $b \leq {1 \over 3}$. We assume that the vertex weights are given in unary; for the case of binary vertex weights, a pseudoapproximation algorithm is presented. This problem is of considerable practical significance, especially in VLSI design. The natural algorithm for this problem accumulates sparsest cuts iteratively. One of our main ideas is to give a definition of sparsity, called net-sparsity, that reflects precisely the cost of the cuts accumulated by this algorithm. However, this definition is too precise: we believe it is NP-hard to compute a minimum-net-sparsity cut, even in planar graphs. The rest of our machinery is built to work with this definition and still make it computationally feasible. Toward this end, we use several ideas from the works of Rao.

Item Type:Article
Source:Copyright of this article belongs to Society for Industrial and Applied Mathematics.
ID Code:101270
Deposited On:31 Jan 2018 09:33
Last Modified:31 Jan 2018 09:33

Repository Staff Only: item control page