С.В. Листровой, д-р техн. наук
Украинский государственный университет железнодорожного транспорта
(Украина, 61050, Харьков, пл. Фейрбаха, 7,
тел. (050)9355042, е-mail:
А.В. Сидоренко
(Samsung Electronics Ukraine Company, LLC Samsung R&D Institute Ukraine
(Украина, 01302, Киев, ул. Льва Толстого, 57,
тел. +380509800852, е-mail
Е.С. Листровая, канд. техн. наук
Национальный аэрокосмический университет им. Н.Е. Жуковского
(Украина, 61070, Харьков, ул. Чкалова, 17,
е-mail:
АННОТАЦИЯ
На основі рангового підходу запропоновано метод перерахування максимальних незалежних множин неорієнтованого зв’язного графа з часовою складністю, що в середньому не перевищує O (n6), де n—число вершин у графі, для графів, що не мають розділяючих вершин, розмір яких не перевищує n = 125.
КЛЮЧЕВЫЕ СЛОВА:
максимальна незалежна множина, кліка, вершинне покриття.
СПИСОК ЛИТЕРАТУРЫ
1. Merrifield R.E., Simmons H.E. Topological methods in chemistry. N.Y.: John Wiley &Sons, 1989.
2. Hosoya H. Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons // Bull. Chem. Soc. Jpn. 1971, 44 (9), p. 2332—2339.
3. Miller R.E., Muller D.E. The problem of maximum consistent subsets—IBM Research Report RC-240. 1960. J.T.Watson Research Center, Yorktown Heights, N.Y. Moon J.W., Moser L. On cliques in graphs // Israel J. Math. 1965, vol. 3, p. 23—28.
4. Watson T. Research Center, Yorktown Heights, N.Y. Moon J.W., Moser L. On cliques in graphs // Israel J. Math. 1965, vol. 3, p. 23—28.
5. Harley E., Bonner A., Goodman N. Uniform integration of genome mapping data using intersection graphs // Bioinformatics, 2001, vol. 17, p. 487—494.
6. Moon J. W., Moser L. On cliques in graphs // Israel J. Math, 1965, vol. 3, p. 23—28.
7. Tomita E., Tanaka A., Takahashi H. The worst-case time complexity for generating all maximal cliques and computational experiments // Theoretical Computer Science, 2006, vol. 363, p. 28—42.
8. Prodinger H., Tichy R.F. Fibonacci numbers of graphs // Fibonacci Quart, 1982, 20 (1), p. 16—21.
9. Listrovoy S.V., Minukhin S.V. General Approach to Solving Optimization Problems in Distributed Cjmputing Sysntems and Theory of Intelligence Systems Construction // Journal of automation and information sciences, 2010, vol. 42, N 3, p. 30—46.
10. Листровой С.В., Минухин С.В. Общий подход к решению задач оптимизации в распределенных
вычислительных системах и теории построения интеллектуальных систем // Проблемы управления и информатика, 2010, №2, c. 65—82.
11. Листровой С.В. Метод перечислення максимальних независимых множеств в произвольных неориентированных графах //Электрон. моделирование, 2014, 36,№1, c. 3—17.
12. Listrovoy S.V., Listrovaya E.S., Panchenko S.V., Moiseenko V.I., Kamenev A.U. Mathematical models in computer control systems RAILWAYS and parallel computing. Kharkiv: FOP Brovin O., 2017, 300 p.
ЛИСТРОВОЙ Сергей Владимирович, д-р техн. наук, профессор Украинского государственного университета железнодорожного транспорта (г. Харьков). В 1972 г. окончил Харьковское высшее военное командно-инженерное училище. Область научных исследований — задачи дискретной оптимизации и теории графов и их приложения к анализу вычислительных систем и сетей.
СИДОРЕНКО Андрей Владимирович, вед. инженер-программист фирмы Samsung Electronics Ukraine Company, LLC Samsung R&D Institute Ukraine (г. Киев). В 2001 г. окончил Харьковский военный университет. Область научных исследований — задачи дискретной оптимизации и теории графов и их приложения к анализу вычислительных систем и сетей.
ЛИСТРОВАЯ Елена Сергеевна, канд. техн. наук, доцент кафедры экономики и маркетинга Национального аэрокосмического университета им. Н.Е. Жуковского (г. Харьков), который окончила в 1998 г. Область научных исследований — применение информационных систем в экономической сфере деятельности.