Minmax subtree cover problem on cacti
Let G=(V,E) G = ( V , E ) be a connected graph such that edges and vertices are weighted by nonnegative reals. Let p  be a positive integer. The minmax subtree cover problem (MSC) asks to find a pair (X,T) ( X , T ) of a partition X={X1,X2,,Xp} X = { X 1 , X 2 ,  , X p } of V  and a set T T of p  subtrees T1,T2,,Tp T 1 , T 2 ,  , T p , each Ti T i containing Xi X i so as to minimize the maximum cost of the subtrees, where the cost of Ti T i is defined to be the sum of the weights of edges in Ti T i and the weights of vertices in Xi X i . In this paper, we propose an O(p2n) O ( p 2 n ) time (4-4/(p+1)) ( 4 - 4 / ( p + 1 ) ) -approximation algorithm for the MSC when G is a cactus.
cactus approximation algorithm graph partition np-hard tree vehicle routing