Standard
One Class of Clusterization Problems in Network Models. / Gimadi, Edward; Chesnokov, Danila; Shin, Ekaterina.
2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 42-47 8880249 (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Gimadi, E, Chesnokov, D & Shin, E 2019,
One Class of Clusterization Problems in Network Models. in
2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019., 8880249, 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019, Institute of Electrical and Electronics Engineers Inc., pp. 42-47, 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019, Novosibirsk, Russian Federation,
26.08.2019.
https://doi.org/10.1109/OPCS.2019.8880249
APA
Vancouver
Gimadi E, Chesnokov D, Shin E.
One Class of Clusterization Problems in Network Models. In 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 42-47. 8880249. (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019). doi: 10.1109/OPCS.2019.8880249
Author
Gimadi, Edward ; Chesnokov, Danila ; Shin, Ekaterina. /
One Class of Clusterization Problems in Network Models. 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 42-47 (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019).
BibTeX
@inproceedings{7c6b3865a9e3476891812fb24ee403df,
title = "One Class of Clusterization Problems in Network Models",
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.",
keywords = "acyclic directed graph, algorithm, clustering problem, complexity status, polynomially solvable cases",
author = "Edward Gimadi and Danila Chesnokov and Ekaterina Shin",
note = "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: {\textcopyright} 2019 IEEE. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 ; Conference date: 26-08-2019 Through 30-08-2019",
year = "2019",
month = aug,
doi = "10.1109/OPCS.2019.8880249",
language = "English",
series = "2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "42--47",
booktitle = "2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019",
address = "United States",
}
RIS
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 -
