Algorithmic Graph Theory

Abstract

The workshop 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.

Geometry and Graphs

• Random triangulations of planar point sets (Emo Welzl)
• Dynamic routing in graphs with applications to harbour logistics (Rolf Möhring)
• Page migration in dynamic networks (Friedhelm Meyer auf der Heide)
• Simple coresets for clustering problems (Christian Sohler)

Graph Algorithms

• Parallel matching algorithms (Stefan Hougardy)
• Scheduling malleable tasks with precedence constraints (Klaus Jansen)
• Coloring random graphs (Lefteris Kirousis)
• Faster approximation algorithms for packing and covering problems (Daniel Bienstock)
• Algebraic graph algorithms (Piotr Sankowski)

Game Theory and Graphs

• Graphs, Games and Algorithms (Paul Spirakis)
• Learning wardrop equilibria (Bertold Vöcking)

Graph Structures

• Phylogenetic Trees and $k$-leaf powers (Andreas Brandstädt)
• Arbitrarily vertex decomposable graphs (Mariusz Woźniak)
• Precoloring extension (Margit Voigt)
• On exact algorithms for treewidth (Hans Bodlaender)

There were 10 shorter talks and two special sessions on “Graph Algorithms” (organized by Christian Sohler) and “Graph Colourin” (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.