Practical Realization of Algorithm of Oriented Graph Paths Decomposition

75

Abstract

This study aims to clarify the methodological status program realization of oriented graph paths decomposition. Algorithms of matrix formulation of decomposition table M from multitude of paths, table sorting by NΣ and balance computing explored. On the basis of those algorithms and original algorithm of oriented graph paths decomposition realized Python 3 program. Results for random-generated graph size of 100 vertices computed and time measured. The results obtained can be used to solve the problem of organizing freight rail transportation at the stage of assignment and movement of locomotives. The scientifi c and practical novelty of the work lies in a signifi cant reduction in the dimension of the original problem, which is especially important in the conditions of transport networks of complex topology.

General Information

Keywords: optimization theory, graph optimization, algorithm of directed graph paths decomposition, strongly connected graph, subgraphs

Journal rubric: Optimization Methods

Article type: scientific article

DOI: https://doi.org/10.17759/mda.2020100305

For citation: Zolotarev I.A., Rasskazova V.A. Practical Realization of Algorithm of Oriented Graph Paths Decomposition. Modelirovanie i analiz dannikh = Modelling and Data Analysis, 2020. Vol. 10, no. 3, pp. 60–68. DOI: 10.17759/mda.2020100305. (In Russ., аbstr. in Engl.)

References

  1. Gainanov D.N., Konygin A.V., Rasskazova V.A. Modelling railway freight traffi c using the methods of graph theory and combinatorial optimization. Automation and Remote Control, 2016 vol. 77, no. 11, pp. 1928–1943.
  2. Gainanov D.N., Kibzun A.I., Rasskazova V.A. Theoretical-graph algorithm in the problem on the assignments and transportations of locomotives. Herald of computer and information technologies, 2017, no. 5, pp. 51–56.
  3. Gainanov D.N., Kibzun A.I., Rasskazova V.A. The Decomposition Problem for the Set of Paths in a Directed Graph and Its Application. Automation and Remote Control, 2018, vol. 79, no. 12, pp. 2217–2236.

Information About the Authors

Igor A. Zolotarev, Master's Student, Moscow Aviation Institute (NRU MAI), Moscow, Russia, ORCID: https://orcid.org/0000-0002-6437-2212, e-mail: yngvar.antonsson@gmail.com

Varvara A. Rasskazova, PhD in Physics and Matematics, Associate Professor of Department 804 "Probability Theory and Computer Modeling", Moscow Aviation Institute, (NRU MAI), Moscow, Russia, ORCID: https://orcid.org/0000-0003-4943-3133, e-mail: varvara.rasskazova@mail.ru

Metrics

Views

Total: 208
Previous month: 2
Current month: 8

Downloads

Total: 75
Previous month: 1
Current month: 3