Parameterized Algorithms for Parity Games

DOI10.1007/978-3-662-48054-0_28MaRDI QIDQ2946404zbMATH OpenOpenAlexFDO

Authors Jakub Gajarský, Michael Lampis, Kazuhisa Makino, Valia Mitsou, Sebastian Ordyniak

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://basepub.dauphine.fr/handle/123456789/15525

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Algorithms for Parity Games
• Algorithms for solving parity games
• The fixpoint-iteration algorithm for parity games
• A Deterministic Subexponential Algorithm for Solving Parity Games
• scientific article; zbMATH DE number 1962853
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• A recursive approach to solving parity games in quasipolynomial time
• Universal algorithms for parity games and nested fixpoints

Cites work

• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• A Deterministic Subexponential Algorithm for Solving Parity Games
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• A survey of stochastic -regular games
• An improved algorithm for the evaluation of fixpoint expressions
• Automata, logics, and infinite games. A guide to current research
• Clique-Width and Parity Games
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Decomposition theorems and model-checking for the modal \(\mu\)-calculus
• Digraph measures: Kelly decompositions, games, and orderings
• Entanglement and the complexity of directed graphs
• Fast mu-calculus model checking when tree-width is bounded.
• Graph operations on parity games and polynomial-time algorithms
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite games played on finite graphs
• Memoryless Determinacy of Parity Games
• Memoryless determinacy of parity and mean payoff games: a simple proof
• On model checking for the \(\mu\)-calculus and its fragments
• Parameterized Algorithms for Modular-Width
• Solving Parity Games in Big Steps
• The Complexity of Tree Automata and Logics of Programs
• The complexity of mean payoff games on graphs
• The complexity of stochastic games
• The dag-width of directed graphs

Cited in

(16)

• Recursive algorithm for parity games requires exponential time
• scientific article; zbMATH DE number 7447732 (Why is no real title available?)
• Algorithms for Parity Games
• Deciding Parity Games in Quasi-polynomial Time
• Solving Parity Games on the GPU
• scientific article; zbMATH DE number 1962853 (Why is no real title available?)
• Parity games of bounded tree- and clique-width
• A Multi-Core Solver for Parity Games
• Generalized Parity Games
• A Deterministic Subexponential Algorithm for Solving Parity Games
• A randomized subexponential algorithm for parity games
• Parity game reductions
• The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
• Clique-Width and Parity Games
• Time and parallelizability results for parity games with bounded treewidth
• A CSP-Based Approach for Solving Parity Game

This page was built for publication: Parameterized Algorithms for Parity Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946404)