Speaker：Guohui Ling（University of Alberta）

Time：2021-06-02 10:00

Location：Zoom Meeting ID: 918 3617 8405  Pwd: 107523

Abstract:

Given a directed graph G = (V, E), the k-path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most k to cover all the vertices of V. 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 directed version is seemingly untouched in the literature. We present the first k/2-approximation algorithm, for any k > 3, based on a novel concept of augmenting path to minimize the number of singletons in the partition. Then, for k = 3, we define the second novel kind of augmenting paths and propose an improved 13/9-approximation algorithm.