Next: MINIMUM QUOTIENT CUT
Up: Cuts and Connectivity
Previous: MINIMUM B-BALANCED CUT
and a rational b, .
A partition of V into disjoint sets A, B, and C, such that
no edge has one endpoint in A and one in B.
The size of the separator, i.e., .
- Bad News:
Not approximable within
even for graphs of maximum degree 3
For planar graphs a separator of size
can be found in
polynomial time .
An -approximation algorithm is also a
algorithm for MINIMUM B-BALANCED CUT