Next: MINIMUM K-VERTEX CONNECTED SUBGRAPH
Up: Cuts and Connectivity
Previous: MINIMUM B-VERTEX SEPARATOR
a vertex-weight function
A cut C, i.e., a subset .
The quotient of the cut, i.e.,
where c(C) denotes the sum of the costs of the edges (u,v) such that
w(V') denotes the sum of the weights of the
vertices in V'.
- Good News:
Also called Minimum Flux Cut.
Admits a PTAS for planar graphs .
The generalization to hypergraphs, also called Minimum Net Expansion,
is approximable within
in the uniform vertex-weight case
. Other approximation algorithms for hypergraph partitioning
problems are contained in .