A Parallel Algorithm for Approximating the Minimum Cycle Cover

We address the problem of approximating a minimum cycle cover in parallel. We give the first efficient parallel algorithm for finding an approximation to a minimum cycle cover. Our algorithm finds a cycle cover whose size is within a factor of O(1 + n log n m+n ) of the minimum sized cover using O(log² n) time on (m + n)= log n processors