"Dynamic Dominating Set and Turbo-Charging Greedy Heuristics" by Rodney G. Downey, Judith Egan et al.

Article Title

Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

Authors

Rodney G. Downey, School of Mathematics, Statistics and Operations Research, Victoria University of Wellington, Wellington 600, New Zealand.
Judith Egan, School of Engineering and Information Technology, Charles Darwin University, Darwin, NT 0909, Australia.
Michael R. Fellows, School of Engineering and Information Technology, Charles Darwin University, Darwin, NT 0909, Australia.
Frances A. Rosamond, School of Engineering and Information Technology, Charles Darwin University, Darwin, NT 0909, Australia.
Peter Shaw, School of Engineering and Information Technology, Charles Darwin University, Darwin, NT 0909, Australia.

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.

DOI

https://doi.org/10.1109/TST.2014.6867515

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.

Download

Request a Copy

Included in

Computer Sciences Commons, Electrical and Computer Engineering Commons

COinS