Improved algorithms for path, matching, and packing problems
J. Chen, S. Lu, S. Sze, F. Zhang. Improved Algorithms for Path, Matching, and Packing Problems. In: Proc SODA 2007. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA); 2007 Jan 7-9; New Orleans, Louisiana. 298-307.
Improved randomized and deterministic algorithms are presented for PATH, MATCHING, and PACKING problems. Our randomized algorithms are based on the divide-and-conquer technique, and improve previous best algorithms for these problems. For example, for the k-PATH problem, our randomized algorithm runs in time O(4kk3.42m) and space O(nklogk + m), improving the previous best randomized algorithm for the problem that runs in time O(5.44kkm) and space O(2kkn + m). To achieve improved deterministic algorithms, we study a number of previously proposed de-randomization schemes, and also develop a new derandomization scheme. These studies result in a number of deterministic algorithms: one of time O(4k+o(k)m) for the k-PATH problem, one of time O(2.803kk nlog2 n) for the 3-D MATCHING problem, and one of time O(43k+o(k)n) for the 3-SET PACKING problem. All these significantly improve previous best algorithms for the problems.