کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
478560 | 1446106 | 2011 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A 2-approximation for the maximum satisfying bisection problem A 2-approximation for the maximum satisfying bisection problem](/preview/png/478560.png)
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 ∈ 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 NPNP-complete. In Bazgan et al. (2008) [C. Bazgan, Z. Tuza, D. Vanderpooten, Approximation of satisfactory bisection problems, Journal of Computer and System Sciences 75 (5) (2008) 875–883], the authors present a polynomial-time 3-approximation for maximizing the number of satisfied vertices in a bisection. It remained an open problem whether one could find a (3 − c)-approximation, for c > 0 (see Bazgan et al. (2010) [C. Bazgan, Z. Tuza, D. Vanderpooten, Satisfactory graph partition, variants, and generalizations, European Journal of Operational Research 206 (2) (2010) 271–280]). In this paper, we solve this problem by presenting a polynomial-time 2-approximation algorithm for the maximum number of satisfied vertices in a satisfying bisection.
Journal: European Journal of Operational Research - Volume 210, Issue 2, 16 April 2011, Pages 169–175