A dynamic algorithm for reachability games on trees
Khoussainov, B; Liu, J; Khaliq, I
Permanent link
http://hdl.handle.net/10292/3353Metadata
Show full metadataAbstract
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(logn), where n is the number of nodes in the current graph.