文章基本信息

标题：A RECURSIVE APPROACH TO SOLVING PARITY GAMES IN QUASIPOLYNOMIAL TIME
本地全文：下载
作者：Karoliina Lehtinen ; Paweł Parys ; Sven Schewe 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2022
卷号：18
期号：1
页码：1-18
DOI：10.46298/lmcs-18(1:8)2022
语种：English
出版社：Technical University of Braunschweig
摘要：Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest among the many existing parity game algorithms. However, its complexity is exponential, while currently the state-of-the-art algorithms have quasipolynomial complexity. Here, we present a modification of Zielonka's classic algorithm that brings its complexity down to $n^{O\left(\log\left(1+\frac{d}{\log n}\right)\right)}$, for parity games of size $n$ with $d$ priorities, in line with previous quasipolynomial-time solutions.
关键词：Parity Games;Quasipolynomial algorithm;Zielonka’s algorithm