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 条
  • [31] An Exact Algorithm for the Arrow Placement Problem in Directed Graph Drawings
    Kido, Naoto
    Masuda, Sumio
    Yamaguchi, Kazuaki
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2019, E102A (11) : 1481 - 1489
  • [32] Application of CMSA to the Minimum Positive Influence Dominating Set Problem
    Akbay, Mehmet Anil
    Blum, Christian
    ARTIFICIAL INTELLIGENCE RESEARCH AND DEVELOPMENT, 2021, 339 : 17 - 26
  • [33] A Tree Based Novel Approach for Graph Coloring Problem Using Maximal Independent Set
    Sharma, Prakash C.
    Chaudhari, Narendra S.
    WIRELESS PERSONAL COMMUNICATIONS, 2020, 110 (03) : 1143 - 1155
  • [34] Fixed point results for set-contractions on metric spaces with a directed graph
    Abbas, Mujahid
    Alfuraidan, Monther Rashed
    Khan, Abdul Rahim
    Nazir, Talat
    FIXED POINT THEORY AND APPLICATIONS, 2015, : 1 - 9
  • [35] Fixed point results for set-contractions on metric spaces with a directed graph
    Mujahid Abbas
    Monther Rashed Alfuraidan
    Abdul Rahim Khan
    Talat Nazir
    Fixed Point Theory and Applications, 2015
  • [36] Center of Trapezoid Graph: Application in Selecting Center Location to Set up a Private Hospital
    Nandi, Shaoli
    Mondal, Sukumar
    Samanta, Sovan
    Barman, Sambhu Charan
    Mrsic, Leo
    Kalampakas, Antonios
    MATHEMATICS, 2025, 13 (05)
  • [37] A General Framework for Graph Matching and Its Application in Ontology Matching
    Zang, Yuda
    Wang, Jianyong
    Zhu, Xuan
    WEB-AGE INFORMATION MANAGEMENT, PT I, 2016, 9658 : 365 - 377
  • [38] Connectivity index of a fuzzy graph and its application to human trafficking
    Binu, M.
    Mathew, Sunil
    Mordeson, J. N.
    FUZZY SETS AND SYSTEMS, 2019, 360 : 117 - 136
  • [39] On a Level-Set Characterization of the Value Function of an Integer Program and Its Application to Stochastic Programming
    Trapp, Andrew C.
    Prokopyev, Oleg A.
    Schaefer, Andrew J.
    OPERATIONS RESEARCH, 2013, 61 (02) : 498 - 511
  • [40] The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
    Habibulla, Yusupjan
    Zhao, Jin-Hua
    Zhou, Hai-Jun
    FRONTIERS IN ALGORITHMICS (FAW 2015), 2015, 9130 : 78 - 88
12345