A maximal l-diameter tree cover of a graph G=(V,E) is a spanning subgraph C=(V,EC) of G such that each connected component of C is a tree, C contains no path with more than l edges, and adding any edge in E-EC to C yields either a path of length l+1 or a cycle. For every function f from positive integers to positive integers, the maximal f-diameter tree cover problem (MDTC(f) problem for short) is to find a maximal f(n)-diameter tree cover of G, given an n-node graph G. In this paper, the authors give two parallel algorithms for the MDTC(f) problem. The first algorithm can be implemented in time O(TMSP(n,f(n))+log2n) using polynomial number of processors on an EREW PRAM, where TMSP(n,f(n)) is the time needed to find a maximal set of vertex disjoint paths of length f(n) in a given n-node graph using polynomial number of processors on an EREW PRAM. The authors then show that if suitable restrictions are imposed on the input graph and/or on the magnitude of f, then TMSP(n,f(n))=O(log’kn) for some constant k and thus, for such cases, an NC algorithm is obtained for the MDTC(f) problem. The second algorithm runs in time O{nlog2n/[f(n)+1]} using polynomial number of processors on an EREW PRAM. Thus if f(n)=¦[[n/(log’kn)] for some k≥0, an NC algorithm is obtained for the MDTC(f) problem.
