A Dynamic Algorithm for Reachability Games Played on Trees

Abstract Our goal is to start the investigation of dynamic algorithms for solving games that are played on finite graphs. The dynamic game determinacy problem calls for finding efficient algorithms that decide the winner of the game when the underlying graph undergoes repeated modifications. In this paper, we focus on turn-based reachability games. We provide an algorithm that solves the dynamic reachability game problem on trees. The amortized time complexity of our algorithm is O (log n ), where n is the number of nodes in the current graph.

Authors

• Bakhadyr Khoussainov
• Jiamou Liu
• Imran Khaliq

Keywords

No keywords are indexed for this paper.