Ergebnisse einschränken

A 2-approximation for the maximum satisfying bisection problem

Ries, Bernard ; Zenklusen, Rico

In: European Journal of Operational Research, 2011, vol. 210, no. 2, p. 169-175

Given a graph G =(V, E), a satisfying bisection of G is a partition of the vertex set V into two sets V1, V2, such that |V1| = |V2|, and such that every vertex v in V has at least as many neighbors in its own set as in the other set. The problem of deciding whether a graph G admits such a partition is NP-complete. In Bazgan et al. (2008) [C. Bazgan, Z. Tuza, D. Vanderpooten, Approximation of...