Article ID: | iaor20112722 |
Volume: | 8 |
Issue: | 1 |
Start Page Number: | 2 |
End Page Number: | 17 |
Publication Date: | Feb 2011 |
Journal: | Discrete Optimization |
Authors: | Niedermeier Rolf, Uhlmann Johannes, Fellows Michael R, Guo Jiong, Komusiewicz Christian |
Keywords: | cliques, clustering |
We introduce overlap cluster graph modification problems where, other than in most previous works, the clusters of the target graph may overlap. More precisely, the studied graph problems ask for a minimum number of edge modifications such that the resulting graph consists of clusters (that is, maximal cliques) that may overlap up to a certain amount specified by the overlap number