Efficient Algorithms with Performance Guarantees for Some Problems of Finding Several Cliques in a Complete Undirected Weighted Graph / Gimadi E. Kh.,Kel'manov A. V.,Pyatkin A. V.,Khachai M. Yu. // PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS. - 2015. - V. 289, l. 1. - P. S88-S101.

ISSN/EISSN:

0081-5438 / 1531-8605

Type:

Article

Abstract:

We consider the problem of finding a fixed number of vertex-disjoint cliques of given sizes in a complete undirected weighted graph so that the total weight of vertices and edges in the cliques would be minimal. We show that the problem is strongly NP-hard both in the general case and in two subclasses, which have important applications. An approximation algorithm for this problem is presented. We show that the algorithm finds a solution with a bounded approximation ratio for the considered subclasses of the problem, and the bound is attainable. In the case when the number of cliques to be found is fixed in advance (i.e., is a parameter), the time complexity of the algorithm is polynomial.

Author keywords:

search for vertex-disjoint cliques; minimum total weight of vertices and edges; approximation algorithm; performance guarantee; attainable bounds; metric problem; quadratic Euclidean problem

DOI:

10.1134/S0081543815050089

Web of Science ID:

ISI:000356931500008

Соавторы в МНС:

—

Другие поля

Поле	Значение
Month	JUL
Publisher	MAIK NAUKA/INTERPERIODICA/SPRINGER
Address	233 SPRING ST, NEW YORK, NY 10013-1578 USA
Language	English
EISSN	1531-8605
Research-Areas	Mathematics
Web-of-Science-Categories	Mathematics, Applied; Mathematics
Author-Email	gimadi@math.nsc.ru kelm@math.nsc.ru artem@math.nsc.ru mkhachay@imm.uran.ru
ResearcherID-Numbers	Khachay, Michael/H-3251-2013 Kel'manov, Alexander/Q-9189-2016
ORCID-Numbers	Khachay, Michael/0000-0003-3555-0080 Kel'manov, Alexander/0000-0001-7757-7228
Funding-Acknowledgement	Russian Foundation for Basic Research {[}12-01-00090, 12-01-00093, 13-01-00210, 13-07-00070, 13-07-00181]; Ural Branch of the Russian Academy of Sciences {[}12-01-1017/1, 7B]; Siberian Branch of the Russian Academy of Sciences {[}12-01-1017/1, 7B]; Program for State Support of Leading Universities of the Russian Federation {[}02.A03.21.0006]
Funding-Text	This work was supported by the Russian Foundation for Basic Research (project nos. 12-01-00090, 12-01-00093, 13-01-00210, 13-07-00070, and 13-07-00181), by the Integration Projects of the Ural and Siberian Branches of the Russian Academy of Sciences (projects no. 12-01-1017/1 and 7B), and by the Program for State Support of Leading Universities of the Russian Federation (agreement no. 02.A03.21.0006 of August 27, 2013).
Number-of-Cited-References	19
Usage-Count-Since-2013	1
Journal-ISO	Proc. Steklov Inst. Math.
Doc-Delivery-Number	CL4OD