
Keywords
kernelization, multivariate algorithms, parameterized algorithms, turbo-charging, heuristics
Abstract
The main purpose of this paper is to exposit two very different, but very general, motivational schemes in the art of parameterization and a concrete example connecting them. We introduce a dynamic version of the Dominating Set problem and prove that it is fixed-parameter tractable (FPT). The problem is motivated by settings where problem instances evolve. It also arises in the quest to improve a natural greedy heuristic for the Dominating Set problem.
Publisher
Tsinghua University Press
Recommended Citation
Rodney G. Downey, Judith Egan, Michael R. Fellows et al. Dynamic Dominating Set and Turbo-Charging Greedy Heuristics. Tsinghua Science and Technology 2014, 19(04): 329-337.