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 条
  • [1] The Decomposition Problem for the Set of Paths in a Directed Graph and Its Application
    D. N. Gainanov
    A. I. Kibzun
    V. A. Rasskazova
    Automation and Remote Control, 2018, 79 : 2217 - 2236
  • [2] FINDING K-DISJOINT PATHS IN A DIRECTED PLANAR GRAPH
    SCHRIJVER, A
    SIAM JOURNAL ON COMPUTING, 1994, 23 (04) : 780 - 788
  • [3] ON THE k SHORTEST SIMPLE PATHS PROBLEM IN WEIGHTED DIRECTED GRAPHS
    Roditty, Liam
    SIAM JOURNAL ON COMPUTING, 2010, 39 (06) : 2363 - 2376
  • [4] Node-to-Set Disjoint Paths Problem in a Mobius Cube
    Kocik, David
    Hirai, Yuki
    Kaneko, Keiichi
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2016, E99D (03): : 708 - 713
  • [5] A construction for the hat problem on a directed graph
    Hod, Rani
    Krzywkowski, Marcin
    ELECTRONIC JOURNAL OF COMBINATORICS, 2012, 19 (01):
  • [6] Spectral graph fractional Fourier transform for directed graphs and its application
    Yan, Fang-Jia
    Li, Bing-Zhao
    SIGNAL PROCESSING, 2023, 210
  • [7] On computing the minimum feedback vertex set of a directed graph by contraction operations
    Lin, HM
    Jou, JY
    IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2000, 19 (03) : 295 - 307
  • [8] The Matching Technique of Directed Cyclic Graph for Task Assignment Problem
    Ariffin, Wan Nor Munirah
    Salleh, Shaharuddin
    INTERNATIONAL CONFERENCE ON QUANTITATIVE SCIENCES AND ITS APPLICATIONS (ICOQSIA 2014), 2014, 1635 : 387 - 394
  • [9] Integral Simplex Using Decomposition for the Set Partitioning Problem
    Zaghrouti, Abdelouahab
    Soumis, Francois
    El Hallaoui, Issmail
    OPERATIONS RESEARCH, 2014, 62 (02) : 435 - 449
  • [10] Lossy Reduction Rules for the Directed Feedback Vertex Set Problem
    Behr, Timon
    Storandt, Sabine
    2023 PROCEEDINGS OF THE SYMPOSIUM ON ALGORITHM ENGINEERING AND EXPERIMENTS, ALENEX, 2023, : 53 - 64
12345