Skip to Main content Skip to Navigation
Journal articles

Parity Games on Undirected Graphs

Abstract : We examine the complexity of solving parity games in the special case when the underlying game graph is undirected. For strictly alternating games, that is, when the game graph is bipartite between the nodes of the two players, we observe that the solution can be computed in linear time. In contrast, when the assumption of strict alternation is dropped, we show that the problem is as hard in the undirected case as it is in the general, directed, case.
Document type :
Journal articles
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Olivier Serre Connect in order to contact the contributor
Submitted on : Friday, January 22, 2016 - 2:36:53 PM
Last modification on : Saturday, June 25, 2022 - 9:09:55 PM
Long-term archiving on: : Friday, November 11, 2016 - 4:32:22 PM


Files produced by the author(s)



Dietmar Berwanger, Olivier Serre. Parity Games on Undirected Graphs. Information Processing Letters, Elsevier, 2012, 112 (23), pp.5. ⟨10.1016/j.ipl.2012.08.021⟩. ⟨hal-01260646⟩



Record views


Files downloads