Parameterized Algorithms for Parity Games

DOI10.1007/978-3-662-48054-0_28zbMATH Open1465.68112OpenAlexW2407205665MaRDI QIDQ2946404FDOQ2946404

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

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

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)

Cites Work

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

Cited In (16)

• Title not available (Why is that?)
• Algorithms for Parity Games
• Deciding Parity Games in Quasi-polynomial Time
• Solving Parity Games on the GPU
• Title not available (Why is that?)
• A Multi-Core Solver for Parity Games
• Parity games of bounded tree- and clique-width
• 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
• Recursive algorithm for parity games requires exponential time

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)