Improved deterministic algorithms for weighted matching and packing problems

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

zbMATH Keywords

(\(n,k\))-universal set\(r\)-set packing\(r\)D-matchingrandomized divide-and-conquer

Mathematics Subject Classification ID

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