Исследование некоторых трудноразрешимых задач на классе предфрактальных графов с изменяемым траекторным порождением

Ключевые слова: NP-полные задачи, предфрактальные графы, алгоритм выделения остовного дерева, визуализация графа

Аннотация

Трудноразрешимые задачи на графах, такие как перечисления, выделение подграфов с заданными характеристиками, становятся особо актуальными на больших графах и сетях. При этом изменчивость и динамичность сетевых структур приводит к «дополнительному» усложнению поиска решения задач дискретной оптимизации. Для решения таких задач предлагаются частные постановки с ограничениями, и выделяются подклассы графов, для которых можно найти решения при определенных условиях. В работе предлагается класс предфрактальных графов и исследуются частные постановки NP-полных задач: изоморфизм подграфу, остов ограниченной степени, остов с максимальным числом висячих вершин, сбалансированный полный двудольный подграф, двудольный подграф, планарный подграф. Выделены условия, при которых для некоторых подзадач возможно получить ответ о существовании и построить полиномиальные алгоритмы поиска решений. Для примера предложены алгоритмы поиска остовных деревьев и упаковки двудольных графов. Разработанные алгоритмы являются полиномиальными и основаны на известных алгоритмах, которые используются в виде процедур. В работе фактически предлагается использовать класс предфрактальных графов в качестве инструмента исследования NP-полных задач и выделения условий их разрешимости. Разработка полиномиальных алгоритмов для динамических графов позволит решать с улучшенными характеристиками такие известные прикладные задачи как выделение подграфов в больших динамических сетях — выделение сообществ в социальных сетях; решение многокритериальных задач в транспортно-логистических системах большой размерности; поиск и выделение ddos-атак в криптовалютных системах и многие другие задачи.

Скачивания

Данные скачивания пока не доступны.

Биография автора

Расул Ахматович Кочкаров, Финансовый университет при Правительстве РФ

канд. экон. наук, доц., доцент департамента анализа данных и машинного обучения Финансового университета при Правительстве РФ

Литература

1. Alekseev V. E. (2002) Research of quanti tative and complexity characteristics of hereditary classes of graphs: abstract of dis. ... doctors of physical and mathematical sciences: 01.01.09. Lobachevsky State University of Nizhny Novgorod. Nizhny Novgorod, 2002. 14 p.
2. Hertz A. (1995) Polynomially solvable classes for the maximum stable set problem. Discrete Applied Mathematics. Vol. 60. P. 195–210, DOI
3. Hertz A. (1997) On the use of boolean methods for the computation of the stability number. Discrete Applied Mathematics. Vol. 76. P. 183– 203, DOI
4. Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco : W. H. Freeman and Company, 1979. 338 p.
5. Golumbic M. C. Algorithmic graph theory and perfect graphs. New-York : Academic Press, 1980, DOI
6. Grotschel M., Lovasz L., Schrijver A. (1984) Polynomial algorithms for perfect graphs. Annals of Discrete Mathematics. Vol. 21. P. 325–356, DOI
7. Harary F. Graph theory. California : Addison-Wesley Pub. Co., 1969. 274 p.
8. Iordanskii M. A. (2012) A Constructive Classification of Graphs. Modeling and Analysis of Information Systems. Vol. 19:4. P. 144–153. DOI
9. Kochkarov A. M. Recognition of fractal graphs. Algorithmic approach. Nizhny Arkhyz : RAS SAO, 1998. 170 p.
10. Kochkarov R. A. Problems of multicriteria optimization on multi-weighted prefractal graphs. Moscow : Akademinnovatsiya, 2014. 189 p.
11. Aziz, F., Akbar M. S., Jawad M., Malik A. H., Uddin M. I., Gkoutos G. V. (2021) Graph characterisation using graphlet-based entropies. Pattern Recognition Letters. Vol. 147. P. 100–107. DOI
12. Aziz F., Ullah A., Shah F. (2020) Feature selection and learning for graphlet kernel. Pattern Recognition Letters. Vol. 136. P. 63–70. DOI
13. Moreno L. Q. (2019) Graphlets and Motifs in Biological Networks. Encyclopedia of Bioinformatics and Computational Biology. Vol. 2. P. 814–820. DOI
14. Timoshenko A. V., Kochkarov R. A., Kochkarov A. A. (2021) Identification Conditions for the Solvability of NP-complete Problems for the Class of Prefractal Graphs. Modeling and Analysis of Information Systems. Vol. 28:2. P. 126–135. DOI
15. Kochkarov A. A., Kochkarov R. A., Malinetskii G. G. (2015) Issues of dynamic graph theory. Computational Mathematics and Mathematical Physics. Vol. 55:9. P. 1590–1596. DOI
16. Kochkarov A. A., Kalashnikov N. V., Kochkarov R. A. (2020) Сomparative analysis of community identification algorithms in complex network systems using social networks as an example. Software products and systems. Vol. 2. P. 349–356. DOI
Опубликован
2021-12-18
Как цитировать
Кочкаров, Р. А. (2021). Исследование некоторых трудноразрешимых задач на классе предфрактальных графов с изменяемым траекторным порождением. Вестник ВГУ. Серия: Системный анализ и информационные технологии, (4), 66-82. https://doi.org/10.17308/sait.2021.4/3799
Раздел
Математические методы системного анализа и управления