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.
Type de document :
Article dans une revue
Information Processing Letters, Elsevier, 2012, 112 (23), pp.5. 〈10.1016/j.ipl.2012.08.021〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01260646
Contributeur : Olivier Serre <>
Soumis le : vendredi 22 janvier 2016 - 14:36:53
Dernière modification le : jeudi 11 janvier 2018 - 06:20:14
Document(s) archivé(s) le : vendredi 11 novembre 2016 - 16:32:22

Fichier

Parity-IPL.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

110

Téléchargements de fichiers

76