Faster Deterministic Algorithms for Packing, Matching and t-Dominating Set Problems

2013/06/15 by Shenshi Chen, Chen, Shenshi, Zhixiang Chen +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #cs.DS

paper · pdf · doi:10.48550/arxiv.1306.3602

ISAAC13 Submission. arXiv admin note: substantial text overlap with arXiv:1303.0478

arxiv created 2013/06/15 · openalex publication_date 2013/06/15 · arxiv updated 2013/06/18 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

In this paper, we devise three deterministic algorithms for solving the m-set k-packing, m-dimensional k-matching, and t-dominating set problems in time O^*(5.44^mk), O^*(5.44^(m-1)k) and O^*(5.44^t), respectively. Although recently there has been remarkable progress on randomized solutions to those problems, our bounds make good improvements on the best known bounds for deterministic solutions to those problems.

Citations

• Monomial Testing and Applications

Related

• Deterministic Parameterized Algorithms for Matching and Packing Problems
• Beyond O*(2ⁿ) in domination-type problems
• Asymptotically Optimal Hardness for k-Set Packing and k-Matroid Intersection
• Parameterized Approximation Algorithms for Packing Problems
• Hardness and Approximation Schemes for Discrete Packing and Domination