AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (828.1 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

School of Mathematics, Statistics and Operations Research, Victoria University of Wellington, Wellington 600, New Zealand.
School of Engineering and Information Technology, Charles Darwin University, Darwin, NT 0909, Australia.
Show Author Information

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

kernelizationmultivariate algorithmsparameterized algorithmsturbo-chargingheuristics

References

【1】
【1】
 
 
Crossref Google Scholar
Tsinghua Science and Technology
Volume 19 Issue 4,
August 2014
Pages 329-337
DOI: 10.1109/TST.2014.6867515

{{item.num}}

Comments on this article

Go to comment

< Back to all reports

Review Status: {{reviewData.commendedNum}} Commended , {{reviewData.revisionRequiredNum}} Revision Required , {{reviewData.notCommendedNum}} Not Commended Under Peer Review

Review Comment

Cite this Report
Close
Close
Cite this article:
Downey RG, Egan J, Fellows MR, et al. Dynamic Dominating Set and Turbo-Charging Greedy Heuristics. Tsinghua Science and Technology, 2014, 19(4): 329-337. https://doi.org/10.1109/TST.2014.6867515

995

Views

58

Downloads

9

Crossref

N/A

Web of Science

15

Scopus

0

CSCD
Received: 20 June 2014
Accepted: 27 June 2014
Published: 30 July 2014
© The author(s) 2014