Розробка методу визначення максимальних клік в неорієнтованих графах
DOI:
https://doi.org/10.15587/1729-4061.2017.111056Ключові слова:
кліки в довільному неорієнтованому графі, максимальні кліки, методи для паралельних обчисленьАнотація
Наведені результати теоретичних досліджень пошуку найбільшої кліки на прикладі оптимізації інформаційних систем залізничного транспорту. У більшості аналогічних розробок не описана можливість реалізації подібних методів для паралельних обчислень. Розроблений метод пошуку найбільшої кліки в довільному неорієнтованому графі з часовою складністю O(2n(n2log2n+n))≈O(2n3log2n) і малою похибкою. Ця розробка перспективна для складання алгоритмів паралельної обробки даних
Посилання
- Butenko, V. M. (2008). Yakist informatsiyno-vymiriuvalnykh system na zaliznychnomu transporti Ukrainy. Zb. naukov. prats. UkrDAZT, 99, 151–155.
- Boynik, A. B., Zagariy, G. I., Koshevoy, S. V. et. al. (2008). Diagnostirovanie ustroystv zheleznodorozhnoy avtomatiki i agregatov podvizhnyh edinic. Kharkiv: ChP Izdatel'stvo “Novoe slovo”, 304.
- Listrovyi, S. V., Panchenko, S. V., Moiseienko, V. I., Butenko, V. M. (2017). Matematychne modeliuvannia v rozpodilenykh informatsiino-keruiuchykh systemakh zaliznychnoho transportu. Kharkiv: FOP Brovin O.V., 220.
- Listrovoy, S. V., Minuhin, S. V., Listrovaya, E. S. (2015). Monitoring distributed computing systems on the basis of the determined shortest paths and shortest hamiltonian cycles in a graph. Eastern-European Journal of Enterprise Technologies, 6 (4 (78)), 32–45. doi: 10.15587/1729-4061.2015.56247
- San Segundo, P., Lopez, A., Pardalos, P. M. (2016). A new exact maximum clique algorithm for large and massive sparse graphs. Computers & Operations Research, 66, 81–94. doi: 10.1016/j.cor.2015.07.013
- El Mouelhi, A., Jégou, P., Terrioux, C., Zanuttini, B. (2013). Some New Tractable Classes of CSPs and Their Relations with Backtracking Algorithms. Lecture Notes in Computer Science, 61–76. doi: 10.1007/978-3-642-38171-3_5
- Zhang, S., Wang, J., Wu, Q., Zhan, J. (2014). A fast genetic algorithm for solving the maximum clique problem. 2014 10th International Conference on Natural Computation (ICNC). doi: 10.1109/icnc.2014.6975933
- San Segundo, P., Matia, F., Rodriguez-Losada, D., Hernando, M. (2011). An improved bit parallel exact maximum clique algorithm. Optimization Letters, 7 (3), 467–479. doi: 10.1007/s11590-011-0431-y
- Bykova, V. (2012). The Clique Minimal Separator Decomposition of a Hypergraph. J. of Siberian Federal University. Mathematics Physics, 5 (1), 36–45.
- Bykova, V., Illarionov, R. (2014). On CLIQUE Problem for Sparse Graphs of Large Dimension. Information Technologies and Mathematical Modelling, 69–75. doi: 10.1007/978-3-319-13671-4_9
- Minukhin, S. (2012). Efficient method for single machine total tardiness problem. 2012 IV International Conference “Problems of Cybernetics and Informatics” (PCI). doi: 10.1109/icpci.2012.6486283
- Buchanan, A., Walteros, J. L., Butenko, S., Pardalos, P. M. (2014). Solving maximum clique in sparse graphs: An O(nm+n2d/4) algorithm for d-degenerate graphs. Optimization Letters, 8 (5), 1611–1617. doi: 10.1007/s11590-013-0698-2
- Veremyev, A., Prokopyev, O. A., Butenko, S., Pasiliao, E. L. (2015). Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs. Computational Optimization and Applications, 64 (1), 177–214. doi: 10.1007/s10589-015-9804-y
- Listrovoy, S. V., Tretiak, V. F., Listrovaya, A. S. (1999). Parallel algorithms of calculation process optimization for the Boolean programming problems. Engineering Simulation, 16, 569–579.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2017 Sergey Listrovoy, Volodymyr Butenko, Volodymyr Bryksin, Oleksandra Golovko
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.
