Skip to Main Content

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

An Algorithm for Covering the Vertices of a Directed Graph

 
Audio is AI-generated
144

,

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

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

OpenAlex citations: 0

OpenAlex trends: Railway Systems and Energy Efficiency, Urban Transport Systems Analysis, Transportation Systems and Logistics

Information about the work in OpenAlex

Number of citations: 0

Topics

Railway Systems and Energy Efficiency

This cluster of papers focuses on the optimization of railway scheduling and operations, including train scheduling, railway timetabling, energy efficiency, traffic management, rescheduling algorithms, urban rail systems, regenerative braking, optimal control, passenger demand-oriented planning, and sustainable transportation.

Number of works: 55585  |  Total number of citations: 203187

Topic detailsв OpenAlex

Urban Transport Systems Analysis

This cluster of papers focuses on the planning, modeling, and management of transportation systems, with an emphasis on digital technologies, quality management, urban traffic, dependability, infrastructure, logistics, and cyber security.

Number of works: 46745  |  Total number of citations: 43271

Topic detailsв OpenAlex

Transportation Systems and Logistics

This cluster of papers focuses on the development and improvement of traffic safety systems and infrastructure, including intelligent transportation systems, road infrastructure, vehicle diagnostics, traffic management, and the environmental impact of transportation. It addresses topics such as accident reconstruction, digital technologies in transportation, and the impact of operational factors on environmental safety.

Number of works: 24013  |  Total number of citations: 38397

Topic detailsв OpenAlex

Work details in OpenAlex

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

Published

For citation: Knyazyatov, M.O., Rasskazova, V.A. (2021). An Algorithm for Covering the Vertices of a Directed Graph. Modelling and Data Analysis, 11(1), 33–39. (In Russ.). https://doi.org/10.17759/mda.2021110103

© Knyazyatov M.O., Rasskazova V.A., 2021

License: CC BY-NC 4.0

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

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

Metrics

 Web Views

Whole time: 504
Previous month: 8
Current month: 9

 PDF Downloads

Whole time: 144
Previous month: 5
Current month: 5

 Total

Whole time: 648
Previous month: 13
Current month: 14