Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Dynamic dominating set and turbo-charging greedy heuristics

Downey, Rod, Egan, Judith, Fellows, Michael, Rosamond, Frances and Shaw, Peter (2014). Dynamic dominating set and turbo-charging greedy heuristics. Tsinghua Science & Technology,19(4):329-337.

Document type: Journal Article
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article

Google Scholar Search Google Scholar

IRMA ID 84373604xPUB28
Title Dynamic dominating set and turbo-charging greedy heuristics
Author Downey, Rod
Egan, Judith
Fellows, Michael
Rosamond, Frances
Shaw, Peter
Journal Name Tsinghua Science & Technology
Publication Date 2014
Volume Number 19
Issue Number 4
ISSN 1007-0214   (check CDU catalogue open catalogue search in new window)
Scopus ID 2-s2.0-84905441218
Start Page 329
End Page 337
Total Pages 9
Place of Publication China
Publisher Qinghua Daxue Xuebao Bianjibu,Tsinghua University, Editorial Board
HERDC Category C1 - Journal Article (DIISR)
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 heuristics
kernelization
multivariate algorithms
parameterized algorithms
turbo-charging
DOI http://dx.doi.org/10.1109/TST.2014.6867515   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 34 Abstract Views  -  Detailed Statistics
Created: Wed, 19 Aug 2015, 12:04:48 CST