Geodesic
Efficient algorithms with performance estimates for some problems of finding several cliques in a~complete undirected weighted graph
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 2, pp. 99-112

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the problem of finding a fixed number of vertex-disjoint cliques of fixed sizes in a complete undirected weighted graph with respect to the criterion of minimizing the total weight of vertices and edges in the cliques. We show that the problem is NP-hard in the strong sense both in the general case and in two particular statements, which have important applications. An approximation algorithm for this problem is presented. We show that the algorithm finds a solution with guaranteed performance estimate for the considered subclasses of the problem, and the estimate is attainable in both cases. In the case when the number of cliques to be found is fixed (i.e., is not involved in the statement), the time complexity of the algorithm is polynomial.
Mots-clés : search for vertex-disjoint cliques
Keywords: minimum total weight of vertices and edges, approximation algorithm, performance guarantee, attainable estimates, metric problem, quadratic Euclidean problem. 
@article{TIMM_2014_20_2_a8,
     author = {E. Kh. Gimadi and A. V. Kel'manov and A. V. Pyatkin and M. Yu. Khachai},
     title = {Efficient algorithms with performance estimates for some problems of finding several cliques in a~complete undirected weighted graph},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {99--112},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2014_20_2_a8/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - A. V. Kel'manov
AU  - A. V. Pyatkin
AU  - M. Yu. Khachai
TI  - Efficient algorithms with performance estimates for some problems of finding several cliques in a~complete undirected weighted graph
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2014
SP  - 99
EP  - 112
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2014_20_2_a8/
LA  - ru
ID  - TIMM_2014_20_2_a8
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A A. V. Kel'manov
%A A. V. Pyatkin
%A M. Yu. Khachai
%T Efficient algorithms with performance estimates for some problems of finding several cliques in a~complete undirected weighted graph
%J Trudy Instituta matematiki i mehaniki
%D 2014
%P 99-112
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2014_20_2_a8/
%G ru
%F TIMM_2014_20_2_a8
E. Kh. Gimadi; A. V. Kel'manov; A. V. Pyatkin; M. Yu. Khachai. Efficient algorithms with performance estimates for some problems of finding several cliques in a~complete undirected weighted graph. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 2, pp. 99-112. http://geodesic.mathdoc.fr/item/TIMM_2014_20_2_a8/