Diskretnyi Analiz i Issledovanie Operatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Diskretn. Anal. Issled. Oper., 2016, Volume 23, Issue 3, Pages 5–20 (Mi da849)  
Graph clustering with a constraint on cluster sizes

V. P. Il'evab, S. D. Il'evab, A. A. Navrotskayaab

a Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
b Omsk State University, 55-A Mir Ave., 644077 Omsk, Russia

Abstract: A graph clustering problem (also known as the graph approximation problem) with a constraint on cluster sizes is studied. A new approximation algorithm is presented for this problem and performance guarantee of this algorithm is obtained. It is shown that the problem belongs to class $APX$ for every fixed $p$, where $p$ is the upper bound on the cluster sizes. Ill. 2, bibliogr. 20.

Keywords: clustering, approximation, graph, approximation algorithm, performance guarantee.

Funding Agency Grant Number
Russian Science Foundation 15-11-10009


DOI: https://doi.org/10.17377/daio.2016.23.521

Full text: PDF file (290 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2016, 10:3, 341–348

Bibliographic databases:

UDC: 519.8
Received: 28.12.2015
Revised: 28.03.2016

Citation: V. P. Il'ev, S. D. Il'eva, A. A. Navrotskaya, “Graph clustering with a constraint on cluster sizes”, Diskretn. Anal. Issled. Oper., 23:3 (2016), 5–20; J. Appl. Industr. Math., 10:3 (2016), 341–348

Citation in format AMSBIB
\Bibitem{IleIleNav16}
\by V.~P.~Il'ev, S.~D.~Il'eva, A.~A.~Navrotskaya
\paper Graph clustering with a~constraint on cluster sizes
\jour Diskretn. Anal. Issled. Oper.
\yr 2016
\vol 23
\issue 3
\pages 5--20
\mathnet{http://mi.mathnet.ru/da849}
\crossref{https://doi.org/10.17377/daio.2016.23.521}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3563713}
\elib{https://elibrary.ru/item.asp?id=26129764}
\transl
\jour J. Appl. Industr. Math.
\yr 2016
\vol 10
\issue 3
\pages 341--348
\crossref{https://doi.org/10.1134/S1990478916030042}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84983509297}


Linking options:
  • http://mi.mathnet.ru/eng/da849
  • http://mi.mathnet.ru/eng/da/v23/i3/p5

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    		• Дискретный анализ и исследование операций
    Number of views:
    This page:168
    Full text:55
    References:15
    First page:3
     
    Contact us:
    		  Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2021