A dynamic algorithm for reachability games on trees

Simple item page
aut.researcherLiu, Jiamou
dc.contributor.authorKhoussainov, B
dc.contributor.authorLiu, J
dc.contributor.authorKhaliq, I
dc.contributor.editorKrálovic, R
dc.contributor.editorNiwinski, D
dc.date.accessioned2011-11-27T03:24:00Z
dc.date.accessioned2012-02-09T23:54:43Z
dc.date.available2011-11-27T03:24:00Z
dc.date.available2012-02-09T23:54:43Z
dc.date.copyright2009
dc.date.issued2009
dc.description.abstractOur 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.
dc.format.mediumPaper and Online
dc.identifier.citation24th International Symposium of Mathematical Foundations of Computer Science (MFCS'09, High Tatras, Slovakia, 2009-08-24 - 2009-08-28, vol.Lecture Notes in Computer Science 5734, pages 518 - 529
dc.identifier.doi10.1007/978-3-642-03816-7_41
dc.identifier.isbn3-642-03815-8
dc.identifier.isbn978-3-642-03815-0
dc.identifier.issn0302-9743
dc.identifier.urihttps://hdl.handle.net/10292/3353
dc.publisherSpringer
dc.relation.isreplacedby10292/4236
dc.relation.isreplacedbyhttp://hdl.handle.net/10292/4236
dc.relation.replaceshttp://hdl.handle.net/10292/2809
dc.relation.replaces10292/2809
dc.relation.urihttp://www.springerlink.com/content/vr1g77267833011l/
dc.rightsAn author may self-archive an author-created version of his/her article on his/her own website and or in his/her institutional repository. He/she may also deposit this version on his/her funder’s or funder’s designated repository at the funder’s request or as a result of a legal obligation, provided it is not made publicly available until 12 months after official publication. He/ she may not use the publisher's PDF version, which is posted on www.springerlink.com, for the purpose of self-archiving or deposit. Furthermore, the author may only post his/her version provided acknowledgement is given to the original source of publication and a link is inserted to the published article on Springer's website. The link must be accompanied by the following text: "The final publication is available at www.springerlink.com”. (Please also see Publisher’s Version and Citation)
dc.rights.accessrightsOpenAccess
dc.titleA dynamic algorithm for reachability games on trees
dc.typeConference Contribution
pubs.organisational-data/AUT
pubs.organisational-data/AUT/Design & Creative Technologies
pubs.organisational-data/AUT/Design & Creative Technologies/School of Computing & Mathematical Science
pubs.organisational-data/AUT/PBRF Researchers
pubs.organisational-data/AUT/PBRF Researchers/Design & Creative Technologies PBRF Researchers
pubs.organisational-data/AUT/PBRF Researchers/Design & Creative Technologies PBRF Researchers/DCT C & M Computing
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
paper6.pdf
Size:
198.47 KB
Format:
Adobe Portable Document Format
Description:
Download
Thumbnail Image
Name:
34. MFCS 2009_ Novy Smokove...pdf
Size:
86.11 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
School of Engineering, Computer and Mathematical Sciences - Te Kura Mātai Pūhanga, Rorohiko, Pāngarau