2007 · 108 citations · 21 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsComputational GeometryApproximation AlgorithmsCombinatorial OptimizationRandomized AlgorithmsRandomized ComplexityRandomized ComputationDerandomizationMatchingMatching AlgorithmsMatching ProblemsPackingPacking ProblemsRandomized Graph AlgorithmsSet Packing Problem
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.
21
An introduction to the theory of numbers
Journal of the Franklin Institute · 1960 · 3.7K citations
Michael R. Fellows · Electronic Notes in Theoretical Computer Science · 2002 · 2.9K citations · Full text
Universal classes of hash functions
J.Lawrence Carter, Mark N. Wegman · Journal of Computer and System Sciences · 1979 · 2.6K citations
Noga Alon, Raphael Yuster, Uri Zwick · Journal of the ACM · 1995 · 1K citations · Full text