Improved deterministic algorithms for weighted matching and packing problems

DOI10.1016/j.tcs.2010.10.042zbMath1215.68109MaRDI QIDQ534565

Songjian Lu, Qilong Feng, Jianxin Wang, Yang Liu, Jian'er Chen

Publication date: 18 May 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.042

zbMATH Keywords

(\(n,k\))-universal set; \(r\)-set packing; \(r\)D-matching; randomized divide-and-conquer

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

Related Items

Improved Algorithms for Several Parameterized Problems Based on Random Methods, The \(k\)-distinct language: parameterized automata constructions, An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs, Parameterized approximation algorithms for packing problems, Conditional matching preclusion for the arrangement graphs, Parameterized counting matching and packing: a family of hard problems that admit FPTRAS, Dealing with several parameterized problems by random methods, Parameterized Complexity and Subexponential-Time Computability, Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets, Mixing Color Coding-Related Techniques

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• A faster parameterized algorithm for set packing
• Using nondeterminism to design efficient deterministic algorithms
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• Improved Parameterized Algorithms for Weighted 3-Set Packing
• Faster Algebraic Algorithms for Path and Packing Problems
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• An efficient parameterized algorithm for m-set packing