A dynamic algorithm for reachability games played on trees

Bakhadyr Khoussainov; Jiamou Liu; Imran Khaliq

doi:10.1007/978-3-642-03816-7_41

A dynamic algorithm for reachability games played on trees

Bakhadyr Khoussainov, Jiamou Liu, Imran Khaliq

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Mathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings
Pages	477-488
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-03816-7_41
Publication status	Published - 28 Sep 2009
Externally published	Yes
Event	34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009 - Novy Smokovec, High Tatras, Slovakia Duration: 24 Aug 2009 → 28 Aug 2009

Publication series

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

Conference

Conference	34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009
Country	Slovakia
City	Novy Smokovec, High Tatras
Period	24/08/09 → 28/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

Khoussainov, Bakhadyr ; Liu, Jiamou ; Khaliq, Imran. / A dynamic algorithm for reachability games played on trees. Mathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings. 2009. pp. 477-488 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{dc0a4434020e4b9cb76b9ed9fdff1c50,

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

author = "Bakhadyr Khoussainov and Jiamou Liu and Imran Khaliq",

year = "2009",

month = sep

day = "28",

doi = "10.1007/978-3-642-03816-7_41",

language = "English",

isbn = "3642038158",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "477--488",

booktitle = "Mathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings",

note = "34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009 ; Conference date: 24-08-2009 Through 28-08-2009",

}

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5734 LNCS, pp. 477-488, 34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, 24/08/09. https://doi.org/10.1007/978-3-642-03816-7_41

A dynamic algorithm for reachability games played on trees. / Khoussainov, Bakhadyr; Liu, Jiamou; Khaliq, Imran.

Mathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings. 2009. p. 477-488 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5734 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

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

Access to Document

10.1007/978-3-642-03816-7_41

Link to publication in Scopus