Improved Algorithms for Path, Matching, and Packing Problems Conference Paper uri icon


  • Copyright © 2007 by the Association for Computing Machinery, Inc. and the Society for Industrial and Applied Mathematics. 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(nk log k + 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 derandomization 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.803kkn log2 n) for the 3-d matching problem, and one of time O(43k+o(k)n) for the 3-set packing problem. All these signi cantly improve previous best algorithms for the problems.

author list (cited authors)

  • Chen, J., Lu, S., Sze, S., Zhang, F., & SIAM, A.

publication date

  • January 2007