Prikladnaya Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






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


Prikl. Diskr. Mat., 2019, Number 46, Pages 72–77 (Mi pdm685)  

Mathematical Backgrounds of Informatics and Programming

On generic complexity of the graph clustering problem

A. N. Rybalov

Sobolev Institute of Mathematics, Omsk, Russia

Abstract: Generic-case approach to algorithmic problems was suggested by Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies behavior of algorithms on typical (almost all) inputs and ignores the rest of inputs. In this paper, we study the generic complexity of the problem of clustering graphs. In this problem the structure of relations of objects is presented as a graph: vertices correspond to objects, and edges connect similar objects. It is required to divide a set of objects into disjoint groups (clusters) to minimize the number of connections between clusters and the number of missing links within clusters. It is proved that under the condition $\text {P} \neq NP$ and $P = BPP$, for the graph clustering problem there is no polynomial strongly generic algorithm. A strongly generic algorithm solves a problem not on the whole set of inputs, but on its subset, in which the sequence of frequencies of inputs converges exponentially fast to $1$ with increasing its size.

Keywords: generic complexity, graph clustering.

Funding Agency Grant Number
Russian Science Foundation 18-71-10028


DOI: https://doi.org/10.17223/20710410/46/6

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

Bibliographic databases:

UDC: 510.52

Citation: A. N. Rybalov, “On generic complexity of the graph clustering problem”, Prikl. Diskr. Mat., 2019, no. 46, 72–77

Citation in format AMSBIB
\Bibitem{Ryb19}
\by A.~N.~Rybalov
\paper On generic complexity of~the~graph clustering problem
\jour Prikl. Diskr. Mat.
\yr 2019
\issue 46
\pages 72--77
\mathnet{http://mi.mathnet.ru/pdm685}
\crossref{https://doi.org/10.17223/20710410/46/6}


Linking options:
  • http://mi.mathnet.ru/eng/pdm685
  • http://mi.mathnet.ru/eng/pdm/y2019/i4/p72

    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:64
    Full text:18
    References:3

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021