Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421033 | Discrete Applied Mathematics | 2006 | 10 Pages |
Abstract
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={X1,X2,…,Xp} of V and a set TT of p subtrees T1,T2,…,TpT1,T2,…,Tp, each TiTi containing XiXi so as to minimize the maximum cost of the subtrees, where the cost of TiTi is defined to be the sum of the weights of edges in TiTi and the weights of vertices in XiXi. In this paper, we propose an O(p2n)O(p2n) time (4-4/(p+1))(4-4/(p+1))-approximation algorithm for the MSC when G is a cactus.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hiroshi Nagamochi, Taizo Kawada,