A dynamic algorithm for reachability games played on trees

Bakhadyr Khoussainov, Jiamou Liu, Imran Khaliq

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)

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(logn), where n is the number of nodes in the current graph.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings
Pages477-488
Number of pages12
DOIs
Publication statusPublished - 28 Sep 2009
Externally publishedYes
Event34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009 - Novy Smokovec, High Tatras, Slovakia
Duration: 24 Aug 200928 Aug 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5734 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009
CountrySlovakia
CityNovy Smokovec, High Tatras
Period24/08/0928/08/09

    Fingerprint

Cite this

Khoussainov, B., Liu, J., & Khaliq, I. (2009). A dynamic algorithm for reachability games played on trees. In Mathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings (pp. 477-488). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5734 LNCS). https://doi.org/10.1007/978-3-642-03816-7_41