Local News & Events
-
[November 18, 2005] Stephan Kreutzer
(Humboldt-Universität zu Berlin): DAG-width and parity games
Abstract. Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph is and gives a notion of graph decomposition that proves useful in algorithm development. Tree-width is characterised by a game known as the cops-and-robber game where a number of cops chase a robber on the graph. We consider the natural adaptation of this game to directed graphs and show that monotone strategies in the game yield a measure with an associated notion of graph decomposition that can be seen to describe how close a directed graph is to a directed acyclic graph (DAG). This promises to be useful in developing algorithms on directed graphs. In particular, we show that the problem of determining the winner of a parity game is solvable in polynomial time on graphs of bounded DAG-width. We also consider the relationship between DAG-width and other measures of such as entanglement and directed tree-width. One consequence we obtain is that certain NP-complete problems such as Hamiltonicity and disjoint paths are polynomial-time computable on graphs of bounded DAG-width.
- [November, 2004] Wolfgang Thomas (RWTH Aachen)
- Our local GAMES seminar is held on Thursdays at 14:15 in room 4030 (MIM UW building).
- The seminar of the Applied Logic Group is held on Tuesdays at 14:15 in room 4030 (MIM UW building).
- The Automata Theory Seminar is held on Wednesdays at 14:15 in room 2080 (MIM UW building).
The annual GAMES Meeting 2006 will be held in Cambridge.
Annual Meeting 2005 Paris, September 21 - September 24
Annual Meeting 2004 Bordeaux, September 15 - September 18
Annual Meeting 2003 Vienna, August 30 - September 2
ETAPS 03 Warsaw, April 5 - 13
Fixed Points in Computer Science (a satellite workshop to ETAPS 03), Warsaw, April 12 - 13, 2003
Workshop on Finite Model Theory Bedlewo, March 31 - April 4, 2003
Kick-Off Meeting Edinburgh, September 26 - 28, 2002
