SIAM Journal on Computing · 2009 · 69 citations · 17 references
ComputingComputer ScienceAlgorithmsCombinatoricsOptimizationApproximation AlgorithmsCombinatorial OptimizationGraph AlgorithmsRandomized AlgorithmsRandomized ComplexityRandomized ComputationExponential SpaceMatching AlgorithmsMatching ProblemsNp-hardnessPacking ProblemsPolynomial SpaceRandomized Graph AlgorithmsRandomized Packing Algorithms
We propose a randomized divide-and-conquer technique that leads to improved randomized and deterministic algorithms for NP-hard path, matching, and packing problems. For the parameterized max-path problem, our randomized algorithm runs in time $O(4^{k}k^{2.7}m)$ and polynomial space (where m is the number of edges in the input graph), improving the previous best randomized algorithm for the problem that runs in time $O(5.44^{k}km)$ and exponential space. Our randomized algorithms for the parameterized max r-d matching and max r-set packing problems run in time $4^{(r-1)k}n^{O(1)}$ and polynomial space, improving the previous best algorithms for the problems that run in time $10.88^{rk}n^{O(1)}$ and exponential space. Moreover, our randomized algorithms can be derandomized to result in significantly improved deterministic algorithms for the problems, and they can be extended to solve other matching and packing problems.
17
Michael R. Fellows · Electronic Notes in Theoretical Computer Science · 2002 · 2.9K citations · Full text
Noga Alon, Raphael Yuster, Uri Zwick · Journal of the ACM · 1995 · 1K citations · Full text