The Complexity of Node Blocking for Dags

Details The Complexity of Node Blocking for Dags The Complexity of Node Blocking for Dags

2008-02-24

arxiv.org/abs/0802.3513v1

Journal of Combinatorial Theory, Series A 118 (2011) 248-256

Computer Science

Computer Science and Game Theory

7 pages, 3 figures

Scientific paper

10.1016/j.jcta.2010.03.011

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 tokens, each player can move his type of tokens. The players alternate their moves and the current player $i$ selects one token of type $i$ and moves the token along a directed edge to an unoccupied vertex. If a player cannot make a move then he loses. We consider the problem of determining the complexity of the game: given an arbitrary configuration of tokens in a directed acyclic graph, does the current player has a winning strategy? We prove that the problem is PSPACE-complete.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Node Blocking for Dags does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of Node Blocking for Dags, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Node Blocking for Dags will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-427213