Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

Rod Downey, Judith Egan, Michael Fellows, Frances Rosamond, Peter Shaw

    Research output: Contribution to journalArticle

    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.
    Original languageEnglish
    Pages (from-to)329-337
    Number of pages9
    JournalTsinghua Science and Technology
    Volume19
    Issue number4
    DOIs
    Publication statusPublished - 2014

    Fingerprint Dive into the research topics of 'Dynamic Dominating Set and Turbo-Charging Greedy Heuristics'. Together they form a unique fingerprint.

    Cite this