|
This article is cited in 4 scientific papers (total in 4 papers)
Optimization, System Analysis, and Operations Research
The decomposition problem for the set of paths in a directed graph and its application
D. N. Gainanov, A. I. Kibzun, V. A. Rasskazova Moscow Aviation Institute (National State University), Moscow, Russia
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.
Keywords:
decomposition, directed graph, strongly connected graph, algorithm, locomotive assignment.
Citation:
D. N. Gainanov, A. I. Kibzun, V. A. Rasskazova, “The decomposition problem for the set of paths in a directed graph and its application”, Avtomat. i Telemekh., 2018, no. 12, 142–166; Autom. Remote Control, 79:12 (2018), 2217–2236
Linking options:
https://www.mathnet.ru/eng/at14981 https://www.mathnet.ru/eng/at/y2018/i12/p142
|
Statistics & downloads: |
Abstract page: | 234 | Full-text PDF : | 46 | References: | 37 | First page: | 14 |
|