|
Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2014, Volume 20, Number 2, Pages 99–112
(Mi timm1062)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
Efficient algorithms with performance estimates for some problems of finding several cliques in a complete undirected weighted graph
E. Kh. Gimadiab, A. V. Kel'manovba, A. V. Pyatkinab, M. Yu. Khachaicd a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b Novosibirsk State University
c B. N. Yeltsin Ural Federal University
d Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences
Abstract:
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.
Keywords:
search for vertex-disjoint cliques, minimum total weight of vertices and edges, approximation algorithm, performance guarantee, attainable estimates, metric problem, quadratic Euclidean problem.
Received: 30.01.2014
Citation:
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 Inst. Mat. i Mekh. UrO RAN, 20, no. 2, 2014, 99–112; Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 88–101
Linking options:
https://www.mathnet.ru/eng/timm1062 https://www.mathnet.ru/eng/timm/v20/i2/p99
|
Statistics & downloads: |
Abstract page: | 351 | Full-text PDF : | 74 | References: | 50 | First page: | 16 |
|