Solving Paths Search Problems in Complex Graphs
- Authors: Kudelia V.N1
-
Affiliations:
- «Institute of Network Technologies»
- Issue: Vol 23, No 6 (2024)
- Pages: 1643-1664
- Section: Mathematical modeling and applied mathematics
- URL: https://ogarev-online.ru/2713-3192/article/view/271660
- DOI: https://doi.org/10.15622/ia.23.6.3
- ID: 271660
Cite item
Full Text
Abstract
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.
About the authors
V. N Kudelia
«Institute of Network Technologies»
Email: Kudelia.Viktor@int.spb.ru
17th line V.O. 54-1
References
- 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.
- 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.
- 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.
- Гасников А.В. Об эффективной вычислимости конкурентных равновесий в транспортно-экономических моделях // Математическое моделирование: 2015. Т. 27. № 12. С. 121–136.
- Волков А.С., Баскаков А.Е. Разработка алгоритма многопутевой маршрутизации в программно-конфигурируемых сетях связи // T-Comm: Телекоммуникации и транспорт. 2021. Т. 15. № 9. С. 17–23.
- 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.
- Glasserman P., de Larrea E.L. Maximum Entropy Distributions with Applications to Graph Simulation. Operations Research. 2023. vol. 71. no. 5. pp. 1908–1924.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // М. Мир. 1982. 419 с.
- Батенков К.А. Точные и граничные оценки вероятностей связности сетей связи на основе метода полного перебора типовых состояний // Труды СПИИРАН. 2019. Т. 18. № 5. C. 1093–1118.
- Тимошенко А.В., Кочкаров Р.А., Кочкаров А.А. Выделение условий разрешимости NP-полных задач для класса предфрактальных графов // Моделирование и анализ информационных систем. 2021. Т. 28. № 2. С. 126–135.
- Левин Л.А. Универсальные задачи перебора // Проблемы передачи информации. 1973. Т. 9. № 3. С. 115–116.
- 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.
- Кристофидес Н. Теория графов Алгоритмический подход // М.: Мир, 1978. 432 с.
- 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.
- Куделя В.Н. Методы перечисления путей в графе // Наукоемкие технологии в космических исследованиях Земли. 2023. Т. 15. № 5. С. 28–38.
- 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.
- 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.
- Harary F., Palmer E.M. Graphical enumeration. Academic Press New York and London, 1972. 271 p.
- 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.
- Рыбалов А.Н. О генерической сложности проблемы распознавания гамильтоновых путей // Прикладная дискретная математика. 2021. № 53. С. 120–126.
- Мизин И.А., Богатырев В.А., Кулешов А.П. Сети коммутации пакетов // М. Радио и связь. 1986. 408 с.
Supplementary files
