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 条
  • [41] Synthesis of Multiple Biomass Corridor via Decomposition Approach: A P-graph Application
    How, Bing Shen
    Hong, Boon Hooi
    Lam, Hon Loong
    Friedler, Ferenc
    PRES15: PROCESS INTEGRATION, MODELLING AND OPTIMISATION FOR ENERGY SAVING AND POLLUTION REDUCTION, 2015, 45 : 1363 - 1368
  • [42] Elitism set based particle swarm optimization and its application
    Sun, Yanxia
    Wang, Zenghui
    INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS, 2017, 10 (01) : 1316 - 1329
  • [43] On Weakly Commuting Set-Valued Mappings on a Domain of Sets Endowed with Directed Graph
    Abbas, Mujahid
    Nazir, Talat
    Popovic, Branislav
    Radenovic, Stojan
    RESULTS IN MATHEMATICS, 2017, 71 (3-4) : 1277 - 1295
  • [44] Hierarchical LU Decomposition and Its Application in Tangential Equivalence Principle
    Shao, Hanru
    Hu, Jun
    Guo, Han
    Ye, Fang
    Lu, Wenchun
    Nie, Zaiping
    2012 IEEE ANTENNAS AND PROPAGATION SOCIETY INTERNATIONAL SYMPOSIUM (APSURSI), 2012,
  • [45] A framework for generalized Benders' decomposition and its application to multilevel optimization
    Bolusani, Suresh
    Ralphs, Ted K.
    MATHEMATICAL PROGRAMMING, 2022, 196 (1-2) : 389 - 426
  • [46] On Weakly Commuting Set-Valued Mappings on a Domain of Sets Endowed with Directed Graph
    Mujahid Abbas
    Talat Nazir
    Branislav Popović
    Stojan Radenović
    Results in Mathematics, 2017, 71 : 1277 - 1295
  • [47] Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes
    Dabrowski, Konrad
    Lozin, Vadim
    Mueller, Haiko
    Rautenbach, Dieter
    COMBINATORIAL ALGORITHMS, 2011, 6460 : 1 - +
  • [48] Correlation Tensor Decomposition and Its Application in Spatial Imaging Data
    Deng, Yujia
    Tang, Xiwei
    Qu, Annie
    JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 2023, 118 (541) : 440 - 456
  • [49] The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics
    Eppstein, David
    Spiro, Emma S.
    ALGORITHMS AND DATA STRUCTURES, 2009, 5664 : 278 - +
  • [50] A Set-based Comprehensive Learning Particle Swarm Optimization with Decomposition for Multiobjective Traveling Salesman Problem
    Yu, Xue
    Chen, Wei-Neng
    Hu, Xiao-Min
    Zhang, Jun
    GECCO'15: PROCEEDINGS OF THE 2015 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2015, : 89 - 96
12345