A 2approximation for the maximum satisfying bisection problem
Published in:
 European Journal of Operational Research.  2011, vol. 210, no. 2, p. 169175
English
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 NPcomplete. 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 polynomialtime 3approximation for maximizing the number of satisﬁed vertices in a bisection. It remained an open problem whether one could ﬁnd 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 polynomialtimeapproximation algorithm for the maximum number of satisﬁed vertices in a satisfying bisection.

Faculty
 Faculté des sciences économiques et sociales et du management

Department
 Département d'informatique

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/308583
Statistics
Document views: 13
File downloads: