most citedSettling the complexity of local max-cut (almost) completely

2 citations · 2 across the 1 of their papers we have counts for

collaborators

1 paper

cs.CC2010★ 2 cited

Settling the complexity of local max-cut (almost) completely

Robert Elsaesser, Tobias Tscheuschner

We consider the problem of finding a local optimum for Max-Cut with FLIP-neighborhood, in which exactly one node changes the partition. Schaeffer and Yannakakis (SICOMP, 1991) show…