Desktop tower defense is NP-hard

Vasin Suttichaya

doi:10.1007/978-3-319-60675-0_2

Desktop tower defense is NP-hard

Vasin Suttichaya

Department of Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Trends in Artificial Intelligence
Subtitle of host publication	PRICAI 2016 Workshops - PeHealth 2016, I3A 2016, AIED 2016, AI4T 2016, IWEC 2016, and RSAI 2016, Revised Selected Papers
Editors	Thanaruk Theeramunkong, Patiyuth Pramkeaw, Mahasak Ketcham, Masayuki Numao, Thepchai Supnithi, Narit Hnoohom
Publisher	Springer Verlag
Pages	19-25
Number of pages	7
ISBN (Print)	9783319606743
DOIs	https://doi.org/10.1007/978-3-319-60675-0_2
Publication status	Published - 2017
Event	14th Pacific Rim International Conference on Artificial Intelligence, PRICAI 2016 - Phuket, Thailand Duration: 22 Aug 2016 → 26 Aug 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10004 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th Pacific Rim International Conference on Artificial Intelligence, PRICAI 2016
Country/Territory	Thailand
City	Phuket
Period	22/08/16 → 26/08/16

Keywords

Complexity
Graph theory
Hamiltonian path

Access to Document

10.1007/978-3-319-60675-0_2

Cite this

Suttichaya, V. (2017). Desktop tower defense is NP-hard. In T. Theeramunkong, P. Pramkeaw, M. Ketcham, M. Numao, T. Supnithi, & N. Hnoohom (Eds.), Trends in Artificial Intelligence: PRICAI 2016 Workshops - PeHealth 2016, I3A 2016, AIED 2016, AI4T 2016, IWEC 2016, and RSAI 2016, Revised Selected Papers (pp. 19-25). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10004 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-319-60675-0_2

Suttichaya, Vasin. / Desktop tower defense is NP-hard. Trends in Artificial Intelligence: PRICAI 2016 Workshops - PeHealth 2016, I3A 2016, AIED 2016, AI4T 2016, IWEC 2016, and RSAI 2016, Revised Selected Papers. editor / Thanaruk Theeramunkong ; Patiyuth Pramkeaw ; Mahasak Ketcham ; Masayuki Numao ; Thepchai Supnithi ; Narit Hnoohom. Springer Verlag, 2017. pp. 19-25 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{718e8d01b3254b09827d1f49697a1be6,

title = "Desktop tower defense is NP-hard",

abstract = "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 {\texttimes} 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.",

keywords = "Complexity, Graph theory, Hamiltonian path",

author = "Vasin Suttichaya",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 14th Pacific Rim International Conference on Artificial Intelligence, PRICAI 2016 ; Conference date: 22-08-2016 Through 26-08-2016",

year = "2017",

doi = "10.1007/978-3-319-60675-0\_2",

language = "English",

isbn = "9783319606743",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "19--25",

editor = "Thanaruk Theeramunkong and Patiyuth Pramkeaw and Mahasak Ketcham and Masayuki Numao and Thepchai Supnithi and Narit Hnoohom",

booktitle = "Trends in Artificial Intelligence",

}

Suttichaya, V 2017, Desktop tower defense is NP-hard. in T Theeramunkong, P Pramkeaw, M Ketcham, M Numao, T Supnithi & N Hnoohom (eds), Trends in Artificial Intelligence: PRICAI 2016 Workshops - PeHealth 2016, I3A 2016, AIED 2016, AI4T 2016, IWEC 2016, and RSAI 2016, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10004 LNAI, Springer Verlag, pp. 19-25, 14th Pacific Rim International Conference on Artificial Intelligence, PRICAI 2016, Phuket, Thailand, 22/08/16. https://doi.org/10.1007/978-3-319-60675-0_2

Desktop tower defense is NP-hard. / Suttichaya, Vasin.
Trends in Artificial Intelligence: PRICAI 2016 Workshops - PeHealth 2016, I3A 2016, AIED 2016, AI4T 2016, IWEC 2016, and RSAI 2016, Revised Selected Papers. ed. / Thanaruk Theeramunkong; Patiyuth Pramkeaw; Mahasak Ketcham; Masayuki Numao; Thepchai Supnithi; Narit Hnoohom. Springer Verlag, 2017. p. 19-25 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10004 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Desktop tower defense is NP-hard

AU - Suttichaya, Vasin

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

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

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

KW - Complexity

KW - Graph theory

KW - Hamiltonian path

UR - https://www.scopus.com/pages/publications/85022337090

U2 - 10.1007/978-3-319-60675-0_2

DO - 10.1007/978-3-319-60675-0_2

M3 - Conference contribution

AN - SCOPUS:85022337090

SN - 9783319606743

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 19

EP - 25

BT - Trends in Artificial Intelligence

A2 - Theeramunkong, Thanaruk

A2 - Pramkeaw, Patiyuth

A2 - Ketcham, Mahasak

A2 - Numao, Masayuki

A2 - Supnithi, Thepchai

A2 - Hnoohom, Narit

PB - Springer Verlag

T2 - 14th Pacific Rim International Conference on Artificial Intelligence, PRICAI 2016

Y2 - 22 August 2016 through 26 August 2016

ER -

Suttichaya V. Desktop tower defense is NP-hard. In Theeramunkong T, Pramkeaw P, Ketcham M, Numao M, Supnithi T, Hnoohom N, editors, Trends in Artificial Intelligence: PRICAI 2016 Workshops - PeHealth 2016, I3A 2016, AIED 2016, AI4T 2016, IWEC 2016, and RSAI 2016, Revised Selected Papers. Springer Verlag. 2017. p. 19-25. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-60675-0_2

Desktop tower defense is NP-hard

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this