Options
New deterministic algorithms for solving parity games
Publikationstyp
Conference Paper
Date Issued
2016-03-22
Sprache
English
Author(s)
TORE-URI
Start Page
634
End Page
645
Citation
Theoretical Informatics (LATIN 2016)
Contribution to Conference
Publisher DOI
Publisher
Springer
We study parity games in which one of the two players controls only a small number k of nodes and the other player controls the n−k other nodes of the game. Our main result is a fixed-parameter algorithm that solves bipartite parity games in time kO(k√)⋅O(n3) and general parity games in time (p+k)O(k√)⋅O(pnm), where p denotes the number of distinct priorities and m denotes the number of edges. For all games with k=o(n)
this improves the previously fastest algorithm by Jurdziński, Paterson, and Zwick (SICOMP 2008).
We also obtain novel kernelization results and an improved deterministic algorithm for graphs with small average degree.
this improves the previously fastest algorithm by Jurdziński, Paterson, and Zwick (SICOMP 2008).
We also obtain novel kernelization results and an improved deterministic algorithm for graphs with small average degree.
DDC Class
004: Informatik