2 papers
cs.DM2021
Algorithms, hardness and graph products on a pursuit-evasion game
Eurinardo Costa, Nicolas Martins, Rudini Sampaio
In the -spy game over a graph, introduced by Cohen et al. in 2016, one spy and guards occupy vertices of a graph and, at each turn, each guard may move along one edge an…
cs.DM2019
Hardness of some variants of the graph coloring game
Thiago Marcilon, Nicolas Martins, Rudini Sampaio
Very recently, a long-standing open question proposed by Bodlaender in 1991 was answered: the graph coloring game is PSPACE-complete. In 2019, Andres and Lock proposed five variant…