GROW 2009

Fourth workshop on Graph Classes, Optimization, and Width Parameters - Bergen, Norway, October 15-17, 2009

Main content

This is a continuation of the series of meetings: Barcelona 2001,  Prague 2005, and Eugene 2007. As with each of the previous GROW workshops, a special issue of Discrete Applied Mathematics is dedicated to papers related to GROW 2009.


GROW 2009 dedicates October 16 to honor Dieter Kratsch on  the occasion of his 50th birthday. That day's program consists of talks related to Dieter's work.


The conference and accommodation for all participants will be organized at Grand Hotel Terminus in Bergen. The organizers take care of everybody's accommodation according to registered dates.


The deadline to submit papers to the special issue of DAM for GROW 2009 is March 1, 2010.


Photos are available under "P & P". New photos added January 20.


Invited speakers

Confirmed invited speakers

Ken-ichi Kawarabayashi   Tokyo National Institute of Informatics
Jaroslav Nesetril   Charles University of Prague
Kristina Vuskovic    University of Leeds



Organizing and scientific committee

Fedor Fomin
Pinar Heggernes (chair)
Jan Kratochvil
Jesper Nederlof
Andrzej Proskurowski
Yngve Villanger



Scientific and social program

All scientific sessions are in the big lecture room Terminus Hall.

Wednesday, October 14
17:00 Registration desk opens (hotel lobby)
19:00-21:00 Welcoming reception (hotel whisky bar)
Thursday, October 15
08:15-08:30 Pinar Heggernes: Opening of the workshop, welcome, history, and practical information

Invited lecture

Kristina Vuskovic: The power of decomposition

09:30-10:00 Jakub Marecek: Some probabilistic results on width parameters of graphs
10:00-10:30 Joonkyung Lee: The rank-width of random graphs
10:30-11:00 Coffee break
11:00-11:30 David Knipe: On the relationship between treewidth, cliquewidth, and degeneracy
11:30-12:00 Robert Ganian: Directed width measures for parameterized algorithms
12:00-12:30 Jan Arne Telle: Comparing width parameters for graphs
12:30-14:00 Lunch

Invited lecture

Ken-ichi Kawarabayashi: The disjoint paths problem - algorithms and structure

15:00-16:00 Open problems / discussions session
16:00-16:30 Coffee break
16:30-17:00 Marcin Kaminski: Induced packing of odd cycles in planar graphs
17:00-17:30 Thomas Erlebach: Approximating node-weighted dominating sets and Steiner subgraphs in unit disk graphs and beyond
17:30-18:00 Tomas Gavenciak: Fast cop games on interval graphs
Friday, October 16
08:15-08:30 Fedor Fomin and Andreas Brandstädt: Opening of the Dieter Kratsch 50th birthday celebration day
08:30-09:00 Jan Kratochvil: Exact algorithms for L(2, 1)-labeling of graphs of bounded degree
09:00-09:30 Derek Corneil: Hamiltonian problems on cocomparability graphs and LexDFS
09:30-10:00 Mathieu Liedloff: On induced and non-induced bicliques
10:00-10:30 Dieter Rautenbach: Bounds on the independence number of a graph
10:30-11:00 Coffee break
11:00-12:30 Open problems / discussions session
12:30-14:00 Lunch
14:00-14:30 Hans Bodlaender: Dynamic programming on tree decompositions using generalised fast subset convolution
14:30-15:00 Ioan Todinca: Constructing brambles
15:00-15:30 Sang-il Oum: Computing rank-width exactly
15:30-16:00 Frederic Mazoit: Tree-width and surface duality
16:00-16:30 Coffee break
16:30-17:00 Yngve Villanger: Finding induced subgraphs via minimal triangulations


Pim van't Hof: On contracting graphs to fixed pattern graphs
17:30-18:00 Daniel Lokshtanov: Iterative localization
19:30 Conference banquet dinner (hotel banquet room Forskjønnelsen)
Saturday, October 17

Invited lecture

Jaroslav Nesetril:Forbidden paths - universality and dualities

09:30-10:00 Daniel Kral: Deciding first order logic properties for sparse graphs
10:00-10:30 Isolde Adler: Treewidth for first order formulas
10:30-11:00 Coffee break
11:00-11:30 Frederic Havet: The spanning galaxy problem
11:30-12:00 Vadim Lozin: Critical properties of bipartite graphs of unbounded clique-width
12:00-12:30 George Mertzios: The recognition of tolerance and bounded tolerance graphs
12:30-14:00 Lunch
14:00-15:30 Open problems / discussions session
15:30 End of workshop


Arrival info

Arrival and practical information

For all registered participants, the accommodation at the conference hotel is taken care of by the organizers, according to the dates they registered with. The participants do not need to contact the hotel prior to arrival.

The hotel is located next to the main train station in the center of Bergen and it is very easy to find. From the airport, there are frequent shuttle buses to the city center. The closest bus stop to the hotel is Bergen main bus terminal (which is not the last stop of the airport shuttle bus).

We encourage all speakers to prepare their talks in a format that can be viewed on and projected from a computer.

There will be free wireless Internet access during the conference.


P & P

Participants and photos

List of registered participants

Group photos and photos by Pinar

Photos by Dieter

Photos by Yushi (login with user: grow and password: grow2009 - please be advised that Yushi will remove the gallery in December, so download the pictures you would like before that)

Photos by Andreas

Photos by Hans

Photos by Jakub




The workshop can be organized thanks to generous support from the Research Council of Norway and NordForsk for which we are grateful.