The Decomposition Problem for the Set of Paths in a Directed Graph and Its Application
- Authors: Gainanov D.N.1, Kibzun A.I.1, Rasskazova V.A.1
-
Affiliations:
- Moscow Aviation Institute (National State University)
- Issue: Vol 79, No 12 (2018)
- Pages: 2217-2236
- Section: Optimization, System Analysis, and Operations Research
- URL: https://journals.rcsi.science/0005-1179/article/view/151105
- DOI: https://doi.org/10.1134/S000511791812010X
- ID: 151105
Cite item
Abstract
We consider the problem of decomposing the set of paths in a directed graph and its application to reducing the dimension of an applied problem on the assignment and transportation of locomotives. On a given set of paths and a set of strongly connected subgraphs, we define a special table. To solve the graph decomposition problem, we develop a heuristic algorithm based on the idea of quicksorting the constructed table. We estimate of the complexity of the resulting algorithm. The obtained results were used to reduce the dimension of the above-mentioned applied problem. We also show the results of computational experiments.
About the authors
D. N. Gainanov
Moscow Aviation Institute (National State University)
Author for correspondence.
Email: damir.gainanov@gmail.com
Russian Federation, Moscow
A. I. Kibzun
Moscow Aviation Institute (National State University)
Email: damir.gainanov@gmail.com
Russian Federation, Moscow
V. A. Rasskazova
Moscow Aviation Institute (National State University)
Email: damir.gainanov@gmail.com
Russian Federation, Moscow
Supplementary files
