Algorithmic Graph Theory

Abstract

The workshop \emph{Algorithmic Graph Theory}, organized by Artur Czumaj (New Jersey), Friedhelm Meyer auf der Heide (Paderborn), Klaus Jansen (Kiel) and Ingo Schiermeyer (Freiberg) was held February 12th--February 18th, 2006. This meeting was attended by 46 participants from a wide range of geographic regions, many of them young researchers. In the morning sessions survey talks providing an overview of recent developments in Algorithmic Graph Theory were presented.

\begin{itemize} \item Geometry and Graphs \begin{itemize} \item Random triangulations of planar point sets (Emo Welzl) \item Dynamic routing in graphs with applications to harbour logistics (Rolf M\"ohring) \item Page migration in dynamic networks (Friedhelm Meyer auf der Heide) \item Simple coresets for clustering problems (Christian Sohler) \end{itemize} \item Graph Algorithms \begin{itemize} \item Parallel matching algorithms (Stefan Hougardy) \item Scheduling malleable tasks with precedence constraints (Klaus Jansen) \item Coloring random graphs (Lefteris Kirousis) \item Faster approximation algorithms for packing and covering problems (Daniel Bienstock) \item Algebraic graph algorithms (Piotr Sankowski) \end{itemize}

\item Game Theory and Graphs \begin{itemize} \item Graphs, Games and Algorithms (Paul Spirakis) \item Learning wardrop equilibria (Bertold V\"ocking) \end{itemize} \item Graph Structures \begin{itemize} \item Phylogenetic Trees and $k$-leaf powers (Andreas Brandst\"adt) \item Arbitrarily vertex decomposable graphs (Mariusz Wo{\'z}niak) \item Precoloring extension (Margit Voigt) \item On exact algorithms for treewidth (Hans Bodlaender) \end{itemize}

\end{itemize}

There were 10 shorter talks and two special sessions on "Graph Algorithms" (organized by Christian Sohler) and "Graph Colouring" (organized by Ingo Schiermeyer). The contributions showed progress in the field provided in recent years. Furthermore, several open problems and conjectures were presented, some of them still far from being resolved. Beyond the program there was plenty of time for the participants to use the stimulating atmosphere of the Oberwolfach Institute for fruitful discussions.