An Algorithm for Covering the Vertices of a Directed Graph



The article presents an algorithm for solving the applied problem of assigning and moving locomotives, based on the solution of the graph–theoretic problem of covering the vertices of a directed graph with a set of oriented paths. A detailed example is given for an algorithm for covering the vertices of a directed graph with a set of maximal paths.

General Information

Keywords: covering the vertices of the graph, moving locomotives, set of paths

Journal rubric: Optimization Methods


For citation: Knyazyatov M.O., Rasskazova V.A. An Algorithm for Covering the Vertices of a Directed Graph. Modelirovanie i analiz dannikh = Modelling and Data Analysis, 2021. Vol. 11, no. 1, pp. 33–39. DOI: 10.17759/mda.2021110103. (In Russ., аbstr. in Engl.)


  1. Lazarev A.A. Estimates of the absolute error and a scheme for an approximate solution to scheduling problems // Computational Mathematics and Mathematical Physics volume49, p. 373–386 (2009).
  2. Lazarev A.A., Gafarov E.R. Transformation of the network graph of scheduling problems with precedence constraints to a planar graph // Doklady Mathematics. 2009. Т. 79. № 1. С. 1–3.
  3. Burdett O., Kozan E. A Disjunctive Graph Model and Framework for Constructing New Train Schedules // Eur. J. Oper. Res. 2010. V. 200. P. 85–98.
  4. Gholami O., Sotskov Y. N. Mixed Graph Model and Algorithms for Parallel Machine Job shop Scheduling Problems // Int. J. Production Research. 2015. V. 8. P. 1–16.
  5. Lusby R., Ryan D. Railway Track Allocation: Models and Methods // Oper. Res. Spektrum. 2011. V. 33. P. 843–883.
  6. Gainanov D.N., Rasskazova V.A. Mathematical modelling of locomotives’ traffic problem by graph theory and combinatorial optimization methods // Moscow Aviation Institute. 2017. № 92.
  7. Gainanov D.N. Combinatoirial geometry and graphs in an analysis of infeasible systems and pattern recognition. M.: Nauka=M.: Science, 2014, 152 p.
  8. Gainanov D.N., Kibzun A.I., Rasskazova V.A. Theoretical-graph Algorithm in the Problem on the Assignments and Transportations of Locomotives // Vestnik computernykh I informatsionnykh tekhnologiy= Bulletin of Computer and Information Technologies. 2017. № 5. p. 51–56.
  9. Gainanov D.N., Rasskazova V.A.. An inference algorithm for monotone boolean functions associated with undirected graphs // Bulletin of the South Ural State University Series Mathematical Modelling Programming and Computer Software. 2016. T. 9. № 3. p. 17–30.

Information About the Authors

Mikhail O. Knyazyatov, student, Moscow aviation Institute (MAI), Moscow, Russia, ORCID:, e-mail:

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:, e-mail:



Total: 209
Previous month: 2
Current month: 2


Total: 64
Previous month: 0
Current month: 0