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


Prikladnaya Diskretnaya Matematika, 2022, Number 57, Pages 91–97
DOI: https://doi.org/10.17223/20710410/57/6
(Mi pdm778)
 

This article is cited in 1 scientific paper (total in 1 paper)

Mathematical Backgrounds of Informatics and Programming

The generic complexity of the bounded problem of graphs clustering

A. N. Rybalov

Sobolev Institute of Mathematics, Omsk, Russia
Full-text PDF (622 kB) Citations (1)
References:
Abstract: Generic-case approach to algorithmic problems studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. In this paper, we study the generic complexity of the bounded problem of graphs clustering. In this problem the structure of objects relations is presented as a graph: vertices correspond to objects, and edges connect similar objects. It is required to divide the set of objects into bounded disjoint groups (clusters) to minimize the number of connections between clusters and the number of missing links within clusters. We have constructed a subproblem of this problem, for which there is no polynomial generic algorithm provided $\text {P} \neq \text{NP}$ and $\text{P} = \text{BPP}$. To prove the theorem, we use the method of generic amplification, which allows to construct generically hard problems from the problems hard in the classical sense. The main component of this method is the cloning technique, which merges the inputs of a problem together into sufficiently large sets of equivalent inputs. Equivalence is understood in the sense that the problem for them is solved in a similar way.
Keywords: generic complexity, graph clustering.
Funding agency Grant number
Russian Science Foundation 22-11-20019
Document Type: Article
UDC: 510.52
Language: Russian
Citation: A. N. Rybalov, “The generic complexity of the bounded problem of graphs clustering”, Prikl. Diskr. Mat., 2022, no. 57, 91–97
Citation in format AMSBIB
\Bibitem{Ryb22}
\by A.~N.~Rybalov
\paper The generic complexity of~the~bounded problem of graphs clustering
\jour Prikl. Diskr. Mat.
\yr 2022
\issue 57
\pages 91--97
\mathnet{http://mi.mathnet.ru/pdm778}
\crossref{https://doi.org/10.17223/20710410/57/6}
Linking options:
  • https://www.mathnet.ru/eng/pdm778
  • https://www.mathnet.ru/eng/pdm/y2022/i3/p91
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Statistics & downloads:
    Abstract page:75
    Full-text PDF :28
    References:22
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024