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. стр. 42-47 8880249 (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Gimadi, E, Chesnokov, D & Shin, E 2019, One Class of Clusterization Problems in Network Models. в 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., стр. 42-47, 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019, Novosibirsk, Российская Федерация, 26.08.2019. https://doi.org/10.1109/OPCS.2019.8880249

APA

Gimadi, E., Chesnokov, D., & Shin, E. (2019). One Class of Clusterization Problems in Network Models. в 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 (стр. 42-47). [8880249] (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/OPCS.2019.8880249

Vancouver

Gimadi E, Chesnokov D, Shin E. 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. стр. 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. стр. 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",
isbn = "9781728129860",
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

UR - https://www.mendeley.com/catalogue/c4496ae6-f5a4-3db9-b319-e4a994072b7a/

U2 - 10.1109/OPCS.2019.8880249

DO - 10.1109/OPCS.2019.8880249

M3 - Conference contribution

AN - SCOPUS:85077975028

SN - 9781728129860

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 -

ID: 26009318