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.
Citation:
I. I. Eremin, E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “$2$-approximate algorithm for finding a clique with minimum weight of vertices and edges”, Trudy Inst. Mat. i Mekh. UrO RAN, 19, no. 2, 2013, 134–143; Proc. Steklov Inst. Math. (Suppl.), 284, suppl. 1 (2014), 87–95