Chen, Jianer; Kneis, Joachim; Lu, Songjian; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter; Sze, Sing-Hoi; Zhang, Fenghui Randomized divide-and-conquer: improved path, matching, and packing algorithms. (English) Zbl 1191.68849 SIAM J. Comput. 38, No. 6, 2526-2547 (2009). Summary: 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. Cited in 37 Documents MSC: 68W20 Randomized algorithms 68Q25 Analysis of algorithms and problem complexity 68R05 Combinatorics in computer science 68W40 Analysis of algorithms Keywords:randomized algorithm; divide-and-conquer; path; matching; set packing PDFBibTeX XMLCite \textit{J. Chen} et al., SIAM J. Comput. 38, No. 6, 2526--2547 (2009; Zbl 1191.68849) Full Text: DOI Link