Parameterized Algorithms for Parity Games
DOI10.1007/978-3-662-48054-0_28zbMath1465.68112OpenAlexW2407205665MaRDI QIDQ2946404
Sebastian Ordyniak, Michael Lampis, Jakub Gajarský, Valia Mitsou, Kazuhisa Makino
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
Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (2)
Cites Work
- Unnamed Item
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- A survey of stochastic \(\omega \)-regular games
- The dag-width of directed graphs
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- Graph operations on parity games and polynomial-time algorithms
- Digraph measures: Kelly decompositions, games, and orderings
- The complexity of stochastic games
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Infinite games played on finite graphs
- The complexity of mean payoff games on graphs
- An improved algorithm for the evaluation of fixpoint expressions
- Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
- Automata, logics, and infinite games. A guide to current research
- Memoryless determinacy of parity and mean payoff games: a simple proof
- Entanglement and the complexity of directed graphs
- Parameterized Algorithms for Modular-Width
- A Deterministic Subexponential Algorithm for Solving Parity Games
- Clique-Width and Parity Games
- The Complexity of Tree Automata and Logics of Programs
- Memoryless Determinacy of Parity Games
- Decomposition theorems and model-checking for the modal μ -calculus
- Solving Parity Games in Big Steps
- Computer Aided Verification
- On model checking for the \(\mu\)-calculus and its fragments
This page was built for publication: Parameterized Algorithms for Parity Games
