We introduce an image segmentation algorithm GC^{max}_{sum}, which combines, in a novel manner,
the strengths of two popular algorithms: Relative Fuzzy Connectedness (RFC) and (standard) Graph Cut (GC).
We show, both theoretically and experimentally, that GC^{max}_{sum}
preserves
robustness of RFC with respect to the seed choice
(thus, avoiding ``shrinking problem'' of GC), while
keeping GC's bigger control over ``leaking though the weak boundary.''
The theoretical analysis of GC^{max}_{sum}
is greatly facilitated by our recent theoretical
results that RFC belongs to the Generalized GC (GGC) segmentation algorithms framework.
In our implementation of GC^{max}_{sum}
we use, as a subroutine, a version of RFC algorithm
(based on
Image Foresting Transform) that runs (provably) in linear time with respect to the image size.
This results in GC^{max}_{sum}
running in a time close to linear.

**ICIP Conference Proceedings reprint.**

**Last modified February 26, 2013.**