This work is devoted to the problem of planning of freight railway transportation. We define a special conflict graph on the basis of a set of acceptable train routes. The investigation aims to solve the classical com...This work is devoted to the problem of planning of freight railway transportation. We define a special conflict graph on the basis of a set of acceptable train routes. The investigation aims to solve the classical combinatorial optimization problem in relation to the maximum independent set of vertices in undirected graphs.The level representation of the graph and its tree are introduced. With use of these constructions, the lower and upper bounds for the number of vertices in the maximum independent set are obtained.展开更多
基金partially supported by the framework of grant number BR05236839.“Development of information technologies and systems for stimulation of personality’s sustainable development as one of the bases of development of digital Kazakhstan.”
文摘This work is devoted to the problem of planning of freight railway transportation. We define a special conflict graph on the basis of a set of acceptable train routes. The investigation aims to solve the classical combinatorial optimization problem in relation to the maximum independent set of vertices in undirected graphs.The level representation of the graph and its tree are introduced. With use of these constructions, the lower and upper bounds for the number of vertices in the maximum independent set are obtained.
