Improved deterministic algorithms for weighted matching and packing problems
From MaRDI portal
Publication:534565
DOI10.1016/j.tcs.2010.10.042zbMath1215.68109OpenAlexW2107174677MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Related Items (10)
An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs ⋮ Mixing Color Coding-Related Techniques ⋮ Parameterized approximation algorithms for packing problems ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Dealing with several parameterized problems by random methods ⋮ Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets ⋮ Conditional matching preclusion for the arrangement graphs ⋮ Improved Algorithms for Several Parameterized Problems Based on Random Methods ⋮ The \(k\)-distinct language: parameterized automata constructions
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
This page was built for publication: Improved deterministic algorithms for weighted matching and packing problems