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
PDF (828.1 KB)
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.

References

[1]
R. M. Karp, Heuristic algorithms in computational molecular biology, J. Comput. Syst. Sci., vol. 77, no. 1, pp. 122-128, 2011.
[2]
L. Cai, J. Chen, R. G. Downey, and M. R. Fellows, On the structure of parameterized problems in NP, Inf. Comput., vol. 123, no. 1, pp. 38-49, 1995.
[3]
L. Cai, J. Chen, R. G. Downey, and M. R. Fellows, Advice classes of parameterized tractability, Ann. Pure Appl. Logic, vol. 84, no. 1, pp. 119-138, 1997.
[4]
L. Cai, J. Chen, R. G. Downey, and M. R. Fellows, On the parameterized complexity of short computation and factorization, Arch. Math. Log., vol. 36, nos. 4-5, pp. 321-337, 1997.
[5]
J. Chen, Randomized disposal of unknowns and implicitly enforced bounds on parameters, in IWPEC, 2008, pp. 1-8.
[6]
J. Chen, Vertex cover kernelization, in Encyclopedia of Algorithms, M. Y. Kao, ed. Springer, 2008.
[7]
J. Chen, Maximum partition matching, in Encyclopedia of Opti-Mization. Kluwer Academic Publishers, 2009, pp. 2029-2035.
[8]
J. Chen and S. B. Cooper, Algorithms, complexity and computational models, Theor. Comput. Sci., vol. 412, no. 23, pp. 2457-2458, 2011.
[9]
J. Chen, H. Fernau, I. A. Kanj, and G. Xia, Parametric duality and kernelization: Lower bounds and upper bounds on kernel size, in STACS, 2005, pp. 269-280.
[10]
J. Chen and I. A. Kanj, Parameterized complexity and subexponential-time computability, in The Multivariate Algorithmic Revolution and Beyond, 2012, pp. 162-195.
[11]
J. Wang, Q. Feng, and J. Chen, Color-coding and its applications: A survey, Int. J. Software and Informatics, vol. 5, no. 4, pp. 595-606, 2011.
[12]
R. G. Downey and M. R. Fellows, Parameterized complexity, in Monographs in Computer Science. Springer-Verlag, New York, 1999.
[13]
R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer-Verlag, London, 2013.
[14]
J. Flum and M. Grohe, Parameterized Complexity Theory. Springer, 2006.
[15]
R. Neidermeier, Invitation to Fixed-Parameter Problems, Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, 2006.
[16]
H.-J. Böckenhauer, J. Hromkovic, and A. Sprock, On the hardness of reoptimization with multiple given solutions, Fundam. Inform., vol. 110, nos. 1-4, pp. 59-76, 2011.
[17]
H.-J. Böckenhauer, J. Hromkovic, T. Mömke, and P. Widmayer, On the hardness of reoptimization, in SOFSEM, volume 4910 of LNCS, Springer, 2008, pp. 50-65.
[18]
U. Stege. Private communication, 1998.
[19]
R. Görke, P. Maillard, C. Staudt, and D. Wagner, Modularity-driven clustering of dynamic graphs, in SEA, 2010, pp. 436-448.
[20]
S. Basu, I. Davidson, and K. Wagstaff, Constrained Clustering: Advances in Algorithms, Theory, and Applications. Chapman and Hall, 2008.
[21]
H. Shachnai, G. Tamir, and T. Tamir, Minimal cost reconfiguration of data placement in a storage area network, Theor. Comput. Sci., vol. 460, pp. 42-53, 2012.
[22]
S. Hartung and R. Niedermeier, Incremental list coloring of graphs, parameterized by conservation, Theoretical Computer Science, 2013.
[23]
R. G. Downey, M. R. Fellows, and U. Stege, Parameterized complexity: A framework for systematically confronting computational intractability, in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999, pp. 49-99.
[24]
H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin, On problems without polynomial kernels, Journal of Computer and System Sciences, vol. 75, no. 8, pp. 423-434, 2009.
[25]
H. L. Bodlaender, S. Thomass’e, and S. Yeo, Kernel bounds for disjoint cycles and disjoint paths, Theoretical Computer Science, vol. 412, no. 35, pp. 4570-4578, 2011.
[26]
L. Fortnow and R. Santhanam, Infeasibility of instance compression and succinct PCPs for NP, in 40th Annual International Symposium on Theory of Computing (STOC 08), 2008, pp. 133-142.
[27]
M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized Complexity. Springer. To appear in 2014 December.
[28]
M. R. Garey and D. S. Johnson, Computers and Intractiblity. A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, 1979.
[29]
M. Dom, D. Lokshtanov, and S. Saurabh, Incompressibility through colors and IDs, in Automata, Languages and Programming. Springer, 2009, pp. 378-389.
[30]
D. Binkele-Raible, H. Fernau, F. V. Fomin, D. Lokshtanov, S. Saurabh, and Y. Villanger, Kernel(s) for problems with no kernel: On out-trees with many leaves, ACM Trans. Algorithms, vol. 8, no. 4, pp. 38:1-38:19, 2012.
Tsinghua Science and Technology
Pages 329-337
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

477

Views

15

Downloads

9

Crossref

N/A

Web of Science

15

Scopus

0

CSCD

Altmetrics

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