One Class of Clusterization Problems in Network Models

Edward Gimadi, Danila Chesnokov, Ekaterina Shin

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

One clustering problem, which arises in design of search systems, is considered. NP-hardness of the general case of the problem is proved. A complexity status is determined for the cases with certain particular structures of the directed graph, such as: Complete Acyclic graph, Path graph, OutTree and InTree graphs. For the cases of Path and InTree graphs the exact algorithms with quadratic complexity are proposed.

Original languageEnglish
Title of host publication2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages42-47
Number of pages6
ISBN (Electronic)9781728129860
DOIs
Publication statusPublished - Aug 2019
Externally publishedYes
Event15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 - Novosibirsk, Russian Federation
Duration: 26 Aug 201930 Aug 2019

Publication series

Name2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019

Conference

Conference15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
CountryRussian Federation
CityNovosibirsk
Period26.08.201930.08.2019

Keywords

  • acyclic directed graph
  • algorithm
  • clustering problem
  • complexity status
  • polynomially solvable cases

Fingerprint

Dive into the research topics of 'One Class of Clusterization Problems in Network Models'. Together they form a unique fingerprint.

Cite this