Solving Paths Search Problems in Complex Graphs

封面

如何引用文章

全文:

详细

The construction of models of various systems is associated with the enumeration of the values of the parameters of the elements of the structure and taking into account all the characteristics of operation and interaction of components to find a certain set of solutions that determine the configuration of the system. Such tasks belong to enumeration type tasks and imply that some of the next solutions from this set are obtained from the previous solution in a certain order. It is known that any problem of the enumeration type is solved only by methods of exhaustive search, and other methods for their enumeration do not exist yet. The paper presents a new method of searching paths in a graph – the method of node-graph transformation. The proposed method, unlike the existing ones, allows one to search all directed simple paths in an oriented graph of arbitrary structure much faster. In the known graph search methods (Breadth First Search and Depth First Search), the object of the search is a path. The total number of such paths in the graph determines the size of the search space. The main idea of the node-graph transformation method is to significantly reduce the size of the search space by enlarging the search objects. The enlargement of enumeration objects is performed by clustering paths into combinatorial objects that concentrate some set of paths of the same length according to certain rules. These combinatorial objects are called node-graphs. A node-graph refers to center-peripheral combinatorial objects, and specific node-graph transformation operations have been developed to enumerate all paths in the graph, which allow finding new paths based on previous paths. The method can be used as a basic toolkit to reduce the dimensionality of the search space for solutions to NP-complete problems while maintaining the universality and accuracy of the full search.

作者简介

V. Kudelia

«Institute of Network Technologies»

Email: Kudelia.Viktor@int.spb.ru
17th line V.O. 54-1

参考

  1. Monch C., Rizk A. Directed Acyclic Graph-Type Distributed Ledgers via Young-Age Preferential Attachment // Stochastic Systems. 2023. vol. 13. no. 3. pp. 377–397.
  2. Chopra S., Park H., Shim S. Extended Graph Formulation for the Inequity Aversion Pricing Problem on Social Networks // INFORMS Journal on Computing. 2022. vol. 34. no. 3. pp. 1327–1344.
  3. Vidal T., Martinelli R., Pham T.A., Ha M.H. Arc Routing with Time-Dependent Travel Times and Paths // Transportation 2021 Science. vol. 55. no. 3. pp. 706–724.
  4. Гасников А.В. Об эффективной вычислимости конкурентных равновесий в транспортно-экономических моделях // Математическое моделирование: 2015. Т. 27. № 12. С. 121–136.
  5. Волков А.С., Баскаков А.Е. Разработка алгоритма многопутевой маршрутизации в программно-конфигурируемых сетях связи // T-Comm: Телекоммуникации и транспорт. 2021. Т. 15. № 9. С. 17–23.
  6. Ray A., Ventresca M., Kannan K. A Graph-Based Ant Algorithm for the Winner Determination Problem in Combinatorial Auctions // Information Systems Research. 2021. vol. 32. no. 4. pp. 1099–1114.
  7. Glasserman P., de Larrea E.L. Maximum Entropy Distributions with Applications to Graph Simulation. Operations Research. 2023. vol. 71. no. 5. pp. 1908–1924.
  8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // М. Мир. 1982. 419 с.
  9. Батенков К.А. Точные и граничные оценки вероятностей связности сетей связи на основе метода полного перебора типовых состояний // Труды СПИИРАН. 2019. Т. 18. № 5. C. 1093–1118.
  10. Тимошенко А.В., Кочкаров Р.А., Кочкаров А.А. Выделение условий разрешимости NP-полных задач для класса предфрактальных графов // Моделирование и анализ информационных систем. 2021. Т. 28. № 2. С. 126–135.
  11. Левин Л.А. Универсальные задачи перебора // Проблемы передачи информации. 1973. Т. 9. № 3. С. 115–116.
  12. Gavanelli M., Mancini T. RCRA 2007: Experimental evaluation of algorithms for solving problems with combinatorial explosion. Journal of Algorithms. 2008. vol. 63. no. 1–3. pp. 1–2. doi: 10.1016/j.jalgor.2008.02.002.
  13. Кристофидес Н. Теория графов Алгоритмический подход // М.: Мир, 1978. 432 с.
  14. Kudelia V.N. Full enumeration methods on graphs // T-Comm. 2023. vol. 17. № 7. pр. 57–64. doi: 10.36724/2072-8735-2023-17-7-57-64.
  15. Куделя В.Н. Методы перечисления путей в графе // Наукоемкие технологии в космических исследованиях Земли. 2023. Т. 15. № 5. С. 28–38.
  16. Ott F., Markovic D., Strobel A., Kiebel S.J. Dynamic integration of forward planning and heuristic preferences during multiple goal pursuit // PLOS Computational Biology. 2020. vol. 16. no. 2. doi: 10.1371/journal.pcbi.1007685.
  17. Banville F., Gravel D., Poisot T. What constrains food webs? A maximum entropy framework for predicting their structure with minimal biases // PLOS Computational Biology. 2023. vol. 19. no. 9. doi: 10.1371/journal.pcbi.1011458.
  18. Harary F., Palmer E.M. Graphical enumeration. Academic Press New York and London, 1972. 271 p.
  19. Kelil A, Dubreuil B, Levy E.D, Michnick S.W. Exhaustive search of linear information encoding protein-peptide recognition. PLOS Computational Biology. 2017. vol. 13. no. 4. doi: 10.1371/journal.pcbi.1005499.
  20. Рыбалов А.Н. О генерической сложности проблемы распознавания гамильтоновых путей // Прикладная дискретная математика. 2021. № 53. С. 120–126.
  21. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети коммутации пакетов // М. Радио и связь. 1986. 408 с.

补充文件

附件文件
动作
1. JATS XML
下载

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».