Improved algorithms for path, matching, and packing problems
Jianer Chen, Songjian Lu, Sing‐Hoi Sze, Fenghui Zhang · 2007
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(4 k k 3.42 m) and space O(nk log k + m), improving the previous best randomized algorithm for the problem that runs in time O(5.44 k km) and space O(2 k kn + m). To achieve improved deterministic algorithms, we study a number of previously proposed derandomization schemes, and also develop a new derandomization scheme. These studies result in a number of deterministic algorithms: one of time O(4 k+o(k) m) for the k-path problem, one of time O(2.80 3k kn log 2 n) for the 3-d matching problem, and one of time O(4 3k+o(k) n) for the 3-set packing problem. All these significantly improve previous best algorithms for the problems.