|
|
单平面有向无圈图中最小路覆盖问题的算法研究
|
Abstract:
一个铁路区段在规划时间内的时空网络是一个仅包含一对源与汇的有向无圈平面图。每个列车都可由该网络中的一条有向路表示。本文研究上述网络中的最小路覆盖问题，即至少用多少条有向路可以覆盖图中所有的边。根据单平面有向无圈图的单源单汇和平面性等结构性质，本文给出了上述问题的一个时间复杂度为O(nk)的精确算法，这里n表示图中顶点数、k表示图中最大有向割所包含边的数目。
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.
| [1] | Caprara, A., Malaguti, E. and Toth, P. (2011) A Freight Service Design Problem for a Railway Corridor. Transportation Science, 45, 147-162. https://doi.org/10.1287/trsc.1100.0348 |
| [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. https://doi.org/10.1109/TSE.1979.234213 |
| [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. https://doi.org/10.1137/0202019 |
| [5] | Even, S. and Tarjan, R.E. (1975) Network Flow and Testing Graph Connec-tivity. SIAM Journal on Computing, 4, 507-518. https://doi.org/10.1137/0204043 |
| [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. https://doi.org/10.1145/48014.61051 |
| [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. https://doi.org/10.1145/2488608.2488705 |
