Parity games on undirected graphs

DOI10.1016/J.IPL.2012.08.021MaRDI QIDQ456183zbMATH OpenOpenAlexFDO

Authors Dietmar Berwanger, Olivier Serre

Publication date 23 October 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01260646/file/Parity-IPL.pdf

zbMATH Keywords

graph algorithmsparity gamesgraph structure complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Games involving graphs (91A43)

Recommendations

• Parity games with partial information played on graphs of bounded complexity
• Algorithms for solving parity games
• Solving parity games via priority promotion
• Solving parity games via priority promotion
• Graph operations on parity games and polynomial-time algorithms

Cites work

• A Deterministic Subexponential Algorithm for Solving Parity Games
• Automata, logics, and infinite games. A guide to current research
• Clique-Width and Parity Games
• DAG-Width and Parity Games
• Digraph measures: Kelly decompositions, games, and orderings
• Fast mu-calculus model checking when tree-width is bounded.
• Logic for Programming, Artificial Intelligence, and Reasoning
• Time and parallelizability results for parity games with bounded treewidth
• Undirected Graphs of Entanglement 2

Cited in

(11)

• Parity in graph sharing games
• scientific article; zbMATH DE number 7533361 (Why is no real title available?)
• Foundations of Software Science and Computation Structures
• Generalized Parity Games
• Graph operations on parity games and polynomial-time algorithms
• Fatal Attractors in Parity Games
• scientific article; zbMATH DE number 7356850 (Why is no real title available?)
• Parity games with partial information played on graphs of bounded complexity
• The mu-calculus and Model Checking
• Parity Games on Graphs with Medium Tree-Width
• scientific article; zbMATH DE number 6374006 (Why is no real title available?)

This page was built for publication: Parity games on undirected graphs

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