RUS  ENG
Full version
JOURNALS // Trudy Instituta Matematiki i Mekhaniki UrO RAN // Archive

Trudy Inst. Mat. i Mekh. UrO RAN, 2013 Volume 19, Number 2, Pages 134–143 (Mi timm939)

This article is cited in 5 papers

$2$-approximate algorithm for finding a clique with minimum weight of vertices and edges

I. I. Eremina, E. Kh. Gimadib, A. V. Kel'manovb, A. V. Pyatkinb, M. Yu. Khachaiac

a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
c Ural Federal University

Abstract: The problem on a minimal clique (with respect to the total weight of its vertices and edges) of fixed size in a complete undirected weighted graph is considered along with some of its important special cases. Approximability questions are analyzed. The weak approximability of the problem is established for the general case. A $2$-approximate effective algorithm with time complexity $O(n^2)$ is proposed for cases where vertex weights are nonnegative and edge weights either satisfy the triangle inequality or are squared pairwise distances for some system of points of a Euclidean space.

Keywords: complete undirected graph, clique of fixed size, minimum weight of vertices and edges, subset search, approximability, polynomial approximation algorithm, performance guarantee, time complexity.

UDC: 519.16+519.85

Received: 10.02.2013


 English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2014, 284, suppl. 1, 87–95

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024