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

https://hal.inria.fr/hal-01260646
Contributor : Olivier Serre <>
Submitted on : Friday, January 22, 2016 - 2:36:53 PM
Last modification on : Saturday, May 1, 2021 - 3:41:11 AM
Long-term archiving on: : Friday, November 11, 2016 - 4:32:22 PM

File

Parity-IPL.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

400

Files downloads

1039