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

被引：0

作者：

Eremin, I. I. ^{[1
,2
,3
]}

Gimadi, E. Kh. ^{[4
,5
]}

Kel'manov, A. V. ^{[4
,5
]}

Pyatkin, A. V. ^{[6
,7
]}

Khachai, M. Yu. ^{[1
,7
]}

机构：

[1] Russian Acad Sci, Moscow, Russia

[2] Russian Acad Sci, Ural Branch, Inst Math & Mech, Moscow, Russia

[3] Russian Acad Sci, Ural Branch, Inst Math & Mech, Physicomath Sci, Moscow, Russia

[4] Russian Acad Sci, Siberian Branch, Sobolev Inst Math, Novosibirsk, Russia

[5] Russian Acad Sci, Siberian Branch, Sobolev Inst Math, Physicomath Sci, Novosibirsk, Russia

[6] Ural Fed Univ, Ekaterinburg, Russia

[7] Ural Fed Univ, Physicomath Sci, Ekaterinburg, Russia

来源：

TRUDY INSTITUTA MATEMATIKI I MEKHANIKI URO RAN | 2013年 / 19卷 / 02期

关键词：

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

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 nonapproximability of the problem is established for the general case. A 2-approximation 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.

引用

页码：134 / 143

页数：10

共 50 条

[1] 2-Approximation Algorithm for Finding a Clique with Minimum Weight of Vertices and Edges
Eremin, I. I.
Gimadi, E. Kh
Kel'manov, A. V.
Pyatkin, A. V.
Khachai, M. Yu
PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS, 2014, 284 : S87 - S95
[2] 2-Approximation algorithm for finding a clique with minimum weight of vertices and edges
I. I. Eremin
E. Kh. Gimadi
A. V. Kel’manov
A. V. Pyatkin
M. Yu. Khachai
Proceedings of the Steklov Institute of Mathematics, 2014, 284 : 87 - 95
[3] A 2-approximation algorithm for the minimum weight edge dominating set problem
Fujito, T
Nagamochi, H
DISCRETE APPLIED MATHEMATICS, 2002, 118 (03) : 199 - 207
[4] A fast 2-approximation algorithm for the Minimum Manhattan Network problem
Guo, Zeyu
Sun, He
Zhu, Hong
ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS, 2008, 5034 : 212 - +
[5] A 2-approximation algorithm for the clustered minimum routing cost tree problem
Lin, Chen-Wan
Wu, Bang Ye
INTELLIGENT SYSTEMS AND APPLICATIONS (ICS 2014), 2015, 274 : 3 - 10
[6] A 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves
Solis-Oba, Roberto
Bonsma, Paul
Lowski, Stefanie
ALGORITHMICA, 2017, 77 (02) : 374 - 388
[7] A 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves
Roberto Solis-Oba
Paul Bonsma
Stefanie Lowski
Algorithmica, 2017, 77 : 374 - 388
[8] How to trim an MST: A 2-approximation algorithm for minimum cost tree cover
Fujito, Toshihiro
AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1, 2006, 4051 : 431 - 442
[9] A 3/2-approximation algorithm for some minimum-cost graph problems
Couetoux, Basile
Davis, James M.
Williamson, David P.
MATHEMATICAL PROGRAMMING, 2015, 150 (01) : 19 - 34
[10] A 2-approximation algorithm 2-ABIS for 2-vertex- connectivity augmentation of specified vertices in a graph
Tamura, M
Taoka, S
Watanabe, T
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2003, E86A (04) : 822 - 828

← 1 2 3 4 5 →