Skip to Main Content

Modelling and Data Analysis
2021. Vol. 11, no. 1, 33–39
doi:10.17759/mda.2021110103
ISSN: 2219-3758 / 2311-9454 (online)

An Algorithm for Covering the Vertices of a Directed Graph

81

M.O. Knyazyatov, V.A. Rasskazova

PDF (RUS)
Online translation in english
GS
Information
in Google Scholar

Abstract

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

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

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.)

References

  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: https://orcid.org/0000-0002-2346-4364, e-mail: mike-99@bk.ru

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: 270
Previous month: 8
Current month: 5

Downloads

Total: 81
Previous month: 2
Current month: 0