Clique-Width and Parity Games

DOI10.1007/978-3-540-74915-8_8MaRDI QIDQ3608404zbMATH OpenOpenAlexFDO

Authors Jan Obdržálek

Publication date 5 March 2009

Published in Computer Science Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74915-8_8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Games involving graphs (91A43)

Recommendations

• Parity games of bounded tree- and clique-width
• Parity Games on Graphs with Medium Tree-Width
• Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width
• Time and parallelizability results for parity games with bounded treewidth
• Parameterized Algorithms for Parity Games

Cited in

(18)

• Solving parity games via priority promotion
• Cliques and constructors in ``Hats game. II
• Digraph width measures in parameterized algorithmics
• Parameterized Algorithms for Parity Games
• Parity games of bounded tree- and clique-width
• Parity Games on Graphs with Medium Tree-Width
• Digraphs of bounded width
• The mu-calculus and Model Checking
• The Descriptive Complexity of Parity Games
• On digraph width measures in parameterized algorithmics
• Alternating traps in Muller and parity games
• Parity in graph sharing games
• The dag-width of directed graphs
• Parity games on undirected graphs
• The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
• The Theory of Universal Graphs for Infinite Duration Games
• The Complexity of Nash Equilibria in Infinite Multiplayer Games
• Graph operations on parity games and polynomial-time algorithms

This page was built for publication: Clique-Width and Parity Games

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