TY - GEN
T1 - A dynamic algorithm for reachability games played on trees
AU - Khoussainov, Bakhadyr
AU - Liu, Jiamou
AU - Khaliq, Imran
PY - 2009/9/28
Y1 - 2009/9/28
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=70349329524&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-03816-7_41
DO - 10.1007/978-3-642-03816-7_41
M3 - Conference contribution
AN - SCOPUS:70349329524
SN - 3642038158
SN - 9783642038150
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 477
EP - 488
BT - Mathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings
T2 - 34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009
Y2 - 24 August 2009 through 28 August 2009
ER -