Title of article
Dynamic Dominating Set and Turbo-Charging Greedy Heuristics
Author/Authors
Downey, Rodney G. Victoria University of Wellington - School of Mathematics, Statistics and Operations Research, New Zealand , Egan, Judith Charles Darwin University - School of Engineering and Information Technology, Australia , Fellows, Michael R. Charles Darwin University - School of Engineering and Information Technology, Australia , Rosamond, Frances A. Charles Darwin University - School of Engineering and Information Technology, Australia , Shaw, Peter Charles Darwin University - School of Engineering and Information Technology, Australia
From page
329
To page
337
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.
Keywords
kernelization , multivariate algorithms , parameterized algorithms , turbo , charging , heuristics
Journal title
Tsinghua Science and Technology
Journal title
Tsinghua Science and Technology
Record number
2535626
Link To Document