Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

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

doi:10.1109/TST.2014.6867515

Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

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

Research output: Contribution to journal › Article › peer-review

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 language	English
Pages (from-to)	329-337
Number of pages	9
Journal	Tsinghua Science and Technology
Volume	19
Issue number	4
DOIs	https://doi.org/10.1109/TST.2014.6867515
Publication status	Published - 2014

Access to Document

10.1109/TST.2014.6867515Licence: Unspecified

Cite this

@article{96394983287e41eb876c652069286732,

title = "Dynamic Dominating Set and Turbo-Charging Greedy 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. ",

keywords = "Technology, Dominating set problems, Dominating sets, Greedy heuristics, heuristics, Kernelization, Parameterized algorithm, Problem instances, turbo-charging, Engineering",

author = "Rod Downey and Judith Egan and Michael Fellows and Frances Rosamond and Peter Shaw",

year = "2014",

doi = "10.1109/TST.2014.6867515",

language = "English",

volume = "19",

pages = "329--337",

journal = "Tsinghua Science and Technology",

issn = "1000-0054",

publisher = "Tsinghua University Press",

number = "4",

}

TY - JOUR

T1 - Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

AU - Downey, Rod

AU - Egan, Judith

AU - Fellows, Michael

AU - Rosamond, Frances

AU - Shaw, Peter

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Technology, Dominating set problems

KW - Dominating sets

KW - Greedy heuristics

KW - heuristics

KW - Kernelization

KW - Parameterized algorithm

KW - Problem instances

KW - turbo-charging, Engineering

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-84905441218&doi=10.1109%2fTST.2014.6867515&origin=inward&txGid=8eaca81d6baed67774a20194a516d882

U2 - 10.1109/TST.2014.6867515

DO - 10.1109/TST.2014.6867515

M3 - Article

VL - 19

SP - 329

EP - 337

JO - Tsinghua Science and Technology

JF - Tsinghua Science and Technology

SN - 1000-0054

IS - 4

ER -

Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

Abstract

Access to Document

Other files and links

Fingerprint

Cite this