25 citations · 119 across the 29 of their papers we have counts for
Showing 2008Show all
3 papers · 1 filter
cs.GT2008★ 3 cited
Phutball is PSPACE-hard
Dariusz Dereniowski
We consider the game of Phutball. It is shown that, given an arbitrary position of stones on the board, it is a PSPACE-hard problem to determine whether the specified p…
cs.GT2008
The Complexity of Node Blocking for Dags
Dariusz Dereniowski
We consider the following modification of annihilation game called node blocking. Given a directed graph, each vertex can be occupied by at most one token. There are two types of t…
math.CO2008★ 4 cited
Maximum vertex occupation time and inert fugitive: recontamination does help
Dariusz Dereniowski
Given a simple graph , we consider the node search problem with inert fugitive. We are interested in minimizing the maximum vertex occupation time, i.e. the maximum number of st…