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

Результат исследований: Вклад в журналСтатьяНаучно-исследовательскаярецензирование

3 Цитирования (Scopus)
Язык оригиналаАнглийский
Страницы (с-по)87-95
Число страниц9
ЖурналProceedings of the Steklov Institute of Mathematics
Том284
Номер выпускаSUPPL.1
DOI
СостояниеОпубликовано - апр 2014

Отпечаток

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

Ключевые слова

    Предметные области ASJC Scopus

    • Mathematics (miscellaneous)

    ГРНТИ

    • 27.00.00 МАТЕМАТИКА

    Уровень публикации

    • Перечень ВАК

    Цитировать

    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. В: Proceedings of the Steklov Institute of Mathematics. 2014 ; Том 284, № SUPPL.1. стр. 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.

    В: Proceedings of the Steklov Institute of Mathematics, Том 284, № SUPPL.1, 04.2014, стр. 87-95.

    Результат исследований: Вклад в журналСтатьяНаучно-исследовательскаярецензирование

    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 -