
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:
Genericcase 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.
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 7277
\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
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 
