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

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)
Original languageEnglish
Pages (from-to)87-95
Number of pages9
JournalProceedings of the Steklov Institute of Mathematics
Volume284
Issue numberSUPPL.1
DOIs
Publication statusPublished - Apr 2014

Fingerprint

Clique
Approximation Algorithms
Inapproximability
Triangle inequality
Approximability
Weighted Graph
Undirected Graph
Time Complexity
Euclidean space
Pairwise
Efficient Algorithms
Non-negative
Configuration
Vertex of a graph

Keywords

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

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

GRNTI

  • 27.00.00 MATHEMATICS

Level of Research Output

  • VAK List

Cite this

Eremin, I. I. ; Gimadi, E. Kh ; Kel'manov, A. V. ; Pyatkin, A. V. ; Khachai, M. Yu. / 2-Approximation Algorithm for Finding a Clique with Minimum Weight of Vertices and Edges. In: Proceedings of the Steklov Institute of Mathematics. 2014 ; Vol. 284, No. SUPPL.1. pp. 87-95.
@article{ed564374e67e4fc9972238c663d5f743,
title = "2-Approximation Algorithm for Finding a Clique with Minimum Weight of Vertices and Edges",
keywords = "approximability, approximation guarantee, clique of fixed size, complete undirected graph, minimum weight of vertices and edges, polynomial time approximation algorithm, subset search, time complexity",
author = "Eremin, {I. I.} and Gimadi, {E. Kh} and Kel'manov, {A. V.} and Pyatkin, {A. V.} and Khachai, {M. Yu}",
year = "2014",
month = "4",
doi = "10.1134/S0081543814020084",
language = "English",
volume = "284",
pages = "87--95",
journal = "Proceedings of the Steklov Institute of Mathematics",
issn = "0081-5438",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "SUPPL.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.

In: Proceedings of the Steklov Institute of Mathematics, Vol. 284, No. SUPPL.1, 04.2014, p. 87-95.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - 2-Approximation Algorithm for Finding a Clique with Minimum Weight of Vertices and Edges

AU - Eremin, I. I.

AU - Gimadi, E. Kh

AU - Kel'manov, A. V.

AU - Pyatkin, A. V.

AU - Khachai, M. Yu

PY - 2014/4

Y1 - 2014/4

KW - approximability

KW - approximation guarantee

KW - clique of fixed size

KW - complete undirected graph

KW - minimum weight of vertices and edges

KW - polynomial time approximation algorithm

KW - subset search

KW - time complexity

UR - http://www.scopus.com/inward/record.url?scp=84898742572&partnerID=8YFLogxK

UR - https://elibrary.ru/item.asp?id=21872446

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000334277400008

U2 - 10.1134/S0081543814020084

DO - 10.1134/S0081543814020084

M3 - Article

VL - 284

SP - 87

EP - 95

JO - Proceedings of the Steklov Institute of Mathematics

JF - Proceedings of the Steklov Institute of Mathematics

SN - 0081-5438

IS - SUPPL.1

ER -