Improved deterministic algorithms for weighted matching and packing problems
From MaRDI portal
Publication:534565
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
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