TWiki> REU Web>GamesOnGraphs (2009-03-12, Main.sr524)EditAttach

Games On Graphs

Must reads

  • NEW! a super-polynomial lower bound for the strategy improvement algorithm for parity games, by Oliver Friedmann (2009).

  • A deterministic subexponential algorithm for solving parity games by Jurdzinksi, Paterson, Zwick (2006).

  • A discrete strategy improvement algorithm for parity games by Jurdzinksi, Voge (2000).

  • Algorithms for Buchi games by Chatterjee, Henzinger, Piterman (2006).

Slides

* Strategy Improvement as sink finding by Hunter.

* Strategy Improvement runs in super-polynomial time by Friedmann.

Theses

* Algorithmic Analysis of Parity Games by Jan Obdrzalek (2006).

* Games and Logical Expressiveness by Dietmar Berwanger (2005).

* Complexity and infinite games on finite graphs by Paul Hunter (2007).

Background

* Complexity Theory (Draft) Arora, Barak.

Edit | Attach | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2009-03-12 - 16:30:26 - Main.sr524
 
This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.