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.
Citation:
D. N. Gainanov, A. I. Kibzun, V. A. Rasskazova, “The decomposition problem for the set of paths in a directed graph and its application”, Avtomat. i Telemekh., 2018, no. 12, 142–166; Autom. Remote Control, 79:12 (2018), 2217–2236
\Bibitem{GaiKibRas18}
\by D.~N.~Gainanov, A.~I.~Kibzun, V.~A.~Rasskazova
\paper The decomposition problem for the set of paths in a directed graph and its application
\jour Avtomat. i Telemekh.
\yr 2018
\issue 12
\pages 142--166
\mathnet{http://mi.mathnet.ru/at14981}
\crossref{https://doi.org/10.31857/S000523100002862-2}
\elib{https://elibrary.ru/item.asp?id=36515656}
\transl
\jour Autom. Remote Control
\yr 2018
\vol 79
\issue 12
\pages 2217--2236
\crossref{https://doi.org/10.1134/S000511791812010X}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000453228600010}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85058287411}
Linking options:
https://www.mathnet.ru/eng/at14981
https://www.mathnet.ru/eng/at/y2018/i12/p142
This publication is cited in the following 4 articles:
L. Yu. Zhilyakova, N. A. Kuznetsov, “Graph methods for solving the unconstrained and constrained optimal assignment problem for locomotives on a single-line railway section”, Autom. Remote Control, 82:5 (2021), 780–797
D. N. Ibragimov, N. M. Novozhilkin, E. Yu. Porceva, “On sufficient optimality conditions for a guaranteed control in the speed problem for a linear time-varying discrete-time system with bounded control”, Autom. Remote Control, 82:12 (2021), 2076–2096
I.A. Zolotarev, V.A. Rasskazova, “Modification of Algorithm of Directed Graph Paths Decomposition with Schedule”, Modelling and Data Analysis, 11:2 (2021), 51
I.A. Zolotarev, V.A. Rasskazova, “Practical Realization of Algorithm of Oriented Graph Paths Decomposition”, Modelling and Data Analysis, 10:3 (2020), 60
Citation in format AMSBIB
Contact us: