TY - GEN
T1 - One Class of Clusterization Problems in Network Models
AU - Gimadi, Edward
AU - Chesnokov, Danila
AU - Shin, Ekaterina
N1 - Funding Information:
Authors are supported by the Russian Foundation for Basic Research (project 16-07-00168), and by the program of fundamental scientific researches of the SB RAS I.5.1.
Publisher Copyright:
© 2019 IEEE.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2019/8
Y1 - 2019/8
N2 - 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.
AB - 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.
KW - acyclic directed graph
KW - algorithm
KW - clustering problem
KW - complexity status
KW - polynomially solvable cases
UR - http://www.scopus.com/inward/record.url?scp=85077975028&partnerID=8YFLogxK
U2 - 10.1109/OPCS.2019.8880249
DO - 10.1109/OPCS.2019.8880249
M3 - Conference contribution
AN - SCOPUS:85077975028
T3 - 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
SP - 42
EP - 47
BT - 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
Y2 - 26 August 2019 through 30 August 2019
ER -