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

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.