Next: MINIMUM K-VERTEX CONNECTED SUBGRAPH
Up: Cuts and Connectivity
Previous: MINIMUM B-VERTEX SEPARATOR
  Index
- INSTANCE:
Graph
,
a vertex-weight function
,
and an
edge-cost function
.
- SOLUTION:
A cut C, i.e., a subset
.
- MEASURE:
The quotient of the cut, i.e.,
where c(C) denotes the sum of the costs of the edges (u,v) such that
either
and
or
and
and, for
any subset
,
w(V') denotes the sum of the weights of the
vertices in V'.
- Good News:
Approximable within
[345].
- Comment:
Also called Minimum Flux Cut.
Admits a PTAS for planar graphs [395].
The generalization to hypergraphs, also called Minimum Net Expansion,
is approximable within
in the uniform vertex-weight case
[368]. Other approximation algorithms for hypergraph partitioning
problems are contained in [368].
Viggo Kann
2000-03-20