Approximation algorithms for the directed path partition problems
Approximation algorithms for the directed path partition problems
复制标题
DOI：
10.1007/978-3-030-97099-4_2
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Yong Chen;Zhi-Zhong Chen;C. Kennedy;Guohui Lin;Yao Xu;An Zhang
中科院分区：
文献类型：
--
作者：
Yong Chen;Zhi-Zhong Chen;C. Kennedy;Guohui Lin;Yao Xu;An Zhang
给定一个有向图，k-路划分问题是寻找一个顶点不相交的有向路的最小集合，每个路的阶至多为k，以覆盖V的所有顶点。该问题在设施定位、网络监控、交通运输等方面有着广泛的应用。它在无向图上的特殊情况最近受到了广泛的关注，但在文献中似乎没有触及到它的一般版本。我们提出的第一个k/2近似算法，任何，基于一个新的概念，增广路径，以尽量减少在分区中的单例数。当，我们提出了一个改进的近似算法的基础上的最大路径循环覆盖其次是一个仔细的2循环消除过程。在此基础上，我们定义了第二类新的增广路，以减少2-路的数目，并提出了一种改进的13/9-近似算法。
Given a digraph, thek-path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at mostkto cover all the vertices ofV. The problem has various applications in facility location, network monitoring, transportation and others. Its special case on undirected graphs has received much attention recently, but the general version is seemingly untouched in the literature. We present the firstk/2-approximation algorithm, for any, based on a novel concept of augmenting path to minimize the number of singletons in the partition. When, we present an improved-approximation algorithm based on the maximum path-cycle cover followed by a careful 2-cycle elimination process. When, we define the second novel kind of augmenting paths to reduce the number of 2-paths and propose an improved 13/9-approximation algorithm.