单平面有向无圈图中最小路覆盖问题的算法研究
Research of Minimum Path Covering Problem Algorithm in Single Planar Directed Acyclic Graph
DOI: 10.12677/AAM.2023.124171, PDF,    科研立项经费支持
作者: 管 锐*, 梁东岳, 杨卫华：太原理工大学数学学院，山西 太原
关键词: 最小路覆盖；有向无圈图；最大有向割；精确算法；Minimum Path Covering； Directed Acyclic Graph； Maximum Directed Cut； Exact Algorithm
摘要: 一个铁路区段在规划时间内的时空网络是一个仅包含一对源与汇的有向无圈平面图。每个列车都可由该网络中的一条有向路表示。本文研究上述网络中的最小路覆盖问题，即至少用多少条有向路可以覆盖图中所有的边。根据单平面有向无圈图的单源单汇和平面性等结构性质，本文给出了上述问题的一个时间复杂度为O(nk)的精确算法，这里n表示图中顶点数、k表示图中最大有向割所包含边的数目。
Abstract: The space-time network of a railway section in the planning time is a directed acyclic graph that contains only a pair of sources and sinks. Each train can be represented by a directed path in the network. In this paper, we study the minimum path covering problem in the above network, that is, at least how many directed paths can cover all edges in the network. According to the structural properties of single-source, single-sink and planarity, we give an O(nk) time exact algorithm to solve the minimum path covering problem in single planar directed acyclic graph, where n is the number of vertices in graph and k is the number of edges in the maximum directed cut.
文章引用：管锐, 梁东岳, 杨卫华. 单平面有向无圈图中最小路覆盖问题的算法研究[J]. 应用数学进展, 2023, 12(4): 1655-1663. https://doi.org/10.12677/AAM.2023.124171

参考文献

[1] Caprara, A., Malaguti, E. and Toth, P. (2011) A Freight Service Design Problem for a Railway Corridor. Transportation Science, 45, 147-162. [Google Scholar] [CrossRef] 
[2] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. The Macmillan Press Ltd, Great Britain.
[3] Ntafos, S.C. and Hakimi, S.L. (1979) On Path Cover Problems in Digraphs and Applications to Program Testing. IEEE Transactions on Software Engineering, SE-5, 520-529. [Google Scholar] [CrossRef] 
[4] Hopcroft, J.E. and Karp, R.M. (1973) An nˆ5/2 Algorithm for Maximum Matchings in Bipartitegraphs. SIAM Journal on Computing, 2, 225-231. [Google Scholar] [CrossRef] 
[5] Even, S. and Tarjan, R.E. (1975) Network Flow and Testing Graph Connec-tivity. SIAM Journal on Computing, 4, 507-518. [Google Scholar] [CrossRef] 
[6] Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. (1993) Network Flows. Prentice Hall, Hoboken.
[7] Goldberg, A.V. and Tarjan, R.E. (1988) A New Approach to the Maximum-Flow Problem. Journal of the ACM, 35, 921-940. [Google Scholar] [CrossRef] 
[8] Orlin, J.B. (2013) Max Flows in o(nm) Time, or Better. Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 765-774. [Google Scholar] [CrossRef] 

为你推荐