Graph clustering with a constraint on cluster sizes
Victor P. Il’ev, Svetlana Il’eva, A. A. Navrotskaya · Journal of Applied and Industrial Mathematics · 2016
A graph clustering problem is under study (also known as the graph approximation problem) with a constraint on cluster sizes. Some new approximation algorithm is presented for this problem, and performance guarantee of the algorithm is obtained. It is shown that the problem belongs to the class APX for every fixed p , where p is the upper bound on the cluster sizes.