Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

作者：Downey Rodney G; Egan Judith; Fellows Michael R; Rosamond Frances A^*; Shaw Peter

来源：Tsinghua Science and Technology, 2014, 19(4): 329-337.

DOI：10.1109/TST.2014.6867515

• kernelization
• multivariate algorithms
• parameterized algorithms
• turbo-charging
• heuristics

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.

• 出版日期2014-8