Improved Algorithms for Path, Matching, and Packing Problems
Conference Paper
Overview
Identity
Additional Document Info
View All
Overview
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