Publication: Desktop tower defense is NP-hard
Issued Date
2017-01-01
Resource Type
ISSN
16113349
03029743
03029743
Other identifier(s)
2-s2.0-85022337090
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol.10004 LNAI, (2017), 19-25
Suggested Citation
Vasin Suttichaya Desktop tower defense is NP-hard. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol.10004 LNAI, (2017), 19-25. doi:10.1007/978-3-319-60675-0_2 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/42391
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Desktop tower defense is NP-hard
Author(s)
Other Contributor(s)
Abstract
© Springer International Publishing AG 2017. This paper proves the hardness of the Desktop Tower Defense game. Specifically, the problem of determining where to locate k turrets in the grid of size n × n in order to maximize the minimum distance from the starting point to the terminating point is shown to be NP-hard. The proof applied to the generalized version of the Desktop Tower Defense.