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

abstract

  • 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.

name of conference

  • Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007

published proceedings

  • PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS

author list (cited authors)

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

complete list of authors

  • Chen, Jianer||Lu, Songjian||Sze, Sing-Hoi||Zhang, Fenghui

publication date

  • January 2007