The Decomposition Problem for the Set of Paths in a Directed Graph and Its Application


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

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.

About the authors

D. N. Gainanov

Moscow Aviation Institute (National State University)

Author for correspondence.
Email: damir.gainanov@gmail.com
Russian Federation, Moscow

A. I. Kibzun

Moscow Aviation Institute (National State University)

Email: damir.gainanov@gmail.com
Russian Federation, Moscow

V. A. Rasskazova

Moscow Aviation Institute (National State University)

Email: damir.gainanov@gmail.com
Russian Federation, Moscow

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2018 Pleiades Publishing, Inc.