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

被引：2
|
作者：
Gainanov, D. N. [1 ]
Kibzun, A. I. [1 ]
Rasskazova, V. A. [1 ]
机构：
[1] Natl State Univ, Moscow Aviat Inst, Moscow, Russia
来源：
AUTOMATION AND REMOTE CONTROL | 2018年 / 79卷 / 12期
关键词：
decomposition; directed graph; strongly connected graph; algorithm; locomotive assignment; ALGORITHM;
D O I：
10.1134/S000511791812010X
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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.
引用
收藏
页码：2217 / 2236
页数：20
相关论文
共 50 条
  • [21] The Polynomial Time Algorithm of the Next-to-shortest Path Problem in Directed Graph
    Zeng, Qinghong
    Yang, Qiaoyan
    2016 PPH INTERNATIONAL CONFERENCE ON SOCIAL SCIENCE AND ENVIRONMENT (PPH-SSE 2016), VOL 2, 2016, 7 : 89 - 92
  • [22] Benders decomposition for the large-scale probabilistic set covering problem
    Liang, Jie
    Yu, Cheng-Yang
    Lv, Wei
    Chen, Wei-Kun
    Dai, Yu-Hong
    COMPUTERS & OPERATIONS RESEARCH, 2025, 177
  • [23] Application of CMSA to the Minimum Capacitated Dominating Set Problem
    Pinacho-Davidson, Pedro
    Bouamama, Salim
    Blum, Christian
    PROCEEDINGS OF THE 2019 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'19), 2019, : 321 - 328
  • [24] Novel Directed Graph Approach for Connection Optimization of the Asymmetric-Paths Winding
    Liang, Yanping
    Guo, Zhongqi
    Wang, Dongmei
    Bian, Xu
    IEEE TRANSACTIONS ON ENERGY CONVERSION, 2019, 34 (04) : 1859 - 1867
  • [25] Decomposition of Complete Bipartite Digraphs and Complete Digraphs into Directed Paths and Directed Cycles of Fixed Even Length
    Shyu, Tay-Woei
    GRAPHS AND COMBINATORICS, 2015, 31 (05) : 1715 - 1725
  • [26] Decomposition of Complete Bipartite Digraphs and Complete Digraphs into Directed Paths and Directed Cycles of Fixed Even Length
    Tay-Woei Shyu
    Graphs and Combinatorics, 2015, 31 : 1715 - 1725
  • [27] Element-free Galerkin method using directed graph and its application to creep problems
    Hagihara, S
    Tsunori, M
    Ikeda, T
    Miyazaki, N
    COMPUTATIONAL MECHANICS, 2003, 31 (06) : 489 - 495
  • [28] Element-free Galerkin method using directed graph and its application to creep problems
    S. Hagihara
    M. Tsunori
    T. Ikeda
    N. Miyazaki
    Computational Mechanics, 2003, 31 : 489 - 495
  • [29] Threshold-Based Responsive Simulated Annealing for Directed Feedback Vertex Set Problem
    Zhang, Qingyun
    Du, Yuming
    Su, Zhouxing
    Li, Chu-Min
    Xu, Junzhou
    Chen, Zhihuai
    Lu, Zhipeng
    THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 18, 2024, : 20856 - 20864
  • [30] DECOMPOSITION OF THE COMPLETE BIPARTITE GRAPH WITH A 1-FACTOR REMOVED INTO PATHS AND STARS
    Lin, Jenq-Jong
    Lee, Hung-Chin
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2018, 13 (02) : 63 - 73
12345