Dynamic Dominating Set and Turbo-Charging Greedy Heuristics |
| |
| Authors: | Rodney G.Downey, Judith Egan, Michael R.Fellows, Frances A.Rosamond, Peter Shaw |
| |
| Affiliation: | [1]School of Mathematics,Statistics and Operations Research, Victoria Universityof Wellington, Wellington 600, New Zealand; [2]School of Engineering and Information Technology, Charles Darwin University,Darwin, NT 0909, Australia |
| |
| 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 |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
