单平面有向无圈图中最小路覆盖问题的算法研究  

Research of Minimum Path Covering Problem Algorithm in Single Planar Directed Acyclic Graph

作　　者：管锐 梁东岳 杨卫华 

机构地区：[1]太原理工大学数学学院,山西 太原

出　　处：《应用数学进展》2023年第4期1655-1663,共9页Advances in Applied Mathematics

摘　　要：一个铁路区段在规划时间内的时空网络是一个仅包含一对源与汇的有向无圈平面图。每个列车都可由该网络中的一条有向路表示。本文研究上述网络中的最小路覆盖问题,即至少用多少条有向路可以覆盖图中所有的边。根据单平面有向无圈图的单源单汇和平面性等结构性质,本文给出了上述问题的一个时间复杂度为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.

关 键 词：最小路覆盖 有向无圈图 最大有向割 精确算法 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]