Workshop program

Wednesday, June 21

16:00 The registration desk opens
19:00 Welcoming reception
20:00 Dinner

Thursday, June 22

08:50-09:00 Welcome and opening
09:00-09:50 Invited talk: Hans BodlaenderComputing Treewidth: Algorithms and Programs
09:50-10:15 Jiri Fiala and Jan Kratochvil Locally injective graph homomorphism: Lists guarantee dichotomy
10:15-10:40 Jan Foniok, Jaroslav Nesetril and Claude TardifGeneralised Dualities and Finite Maximal Antichains
10:40-11:00 Coffee break
11:00-11:25 Daniel MarxChordal deletion is fixed-parameter tractable
11:25-11:55 Christian Knauer and Andreas Spillner A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators
11:55-12:20 Joachim Kneis, Daniel Moelle, Stefan Richter, and Peter Rossmanith Divide-and-Color
12:20-12:45 Masashi Kiyomi, Shuji Kijima, and Takeaki Uno Listing Chordal Graphs and Interval Graphs
12:45-14:00Lunch break
14:00-14:25 Serge Gaspers and Mathieu Liedloff A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs
14:25-14:50 Lukasz Kowalik Improved Edge Coloring with Three Colors
14:50-15:15 Yasuhiko Takenaga and Kenichi Higashide Vertex Coloring of Comparability+ke and -ke Graphs
15:15-15:40 Seok-Hee Hong and Hiroshi NagamochiConvex Drawings of Graphs with Non-Convex Boundary
15:40-16:00 Coffee and cakes
16:00-16:25 Alexander Grigoriev, Joyce van Loon, Rene Sitters, and Marc Uetz How to Sell a Graph: Guidelines for Graph Retailers
16:25-16:50 Magnus M. Halldorsson and Ragnar K. Karlsson Strip Graphs: Recognition and Scheduling
16:50-17:15 Michele Flammini, Luca Moscardelli, Gianpiero Monaco, Mordechai Shalom, and Shmuel Zaks Approximating the Traffic Grooming Problem in Tree and Star Networks
17:15-17:40 Gaurav Goel and Jens Gustedt Bounded Arboricity to Determine the Local Structure of Sparse Graphs
18:00-19:00 Business/PC meeting
20:00 Dinner

Friday, June 23

08:50-09:00 Presentation of WG'07
09:00-90:50 Invited talk: Tandy Warnow Algorithmic issues in Inferring the "Tree of Life"
09:50-10:15 Andrew Curtis, Clemente Izurieta, Benson Joeris, Scott Lundberg, and Ross M. McConnell An Implicit Representation of Chordal Comparability Graphs
10:15-10:40 David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, and Sheng-Lung PengPartitioned Probe Comparability Graphs
10:40-11:00 Coffee break
11:00-11:25 Johann A. Makowsky, Udi Rotics, Ilya Averbouch, and Benny Godlin Computing Graph Polynomials on Graphs of Bounded Clique-Width
11:25-11:55 Christophe Paul, Andrzej Proskurowski, and Jan Arne Telle Generation of edge-maximal graphs with bounded branchwidth
11:55-12:20 Ivan Rapaport, Karol Suchan, and Ioan Todinca Minimal proper interval completions
12:20-12:45 Pierre Fraigniaud and Nicolas Nisse Monotony Properties of Connected Visible Graph Searching
12:45-14:00 Lunch break
14:00-14:25 Marina Lipshteyn, Martin Golumbic, and Michal Stern Finding Intersection Models of Weakly Chordal Graphs
14:25-14:50 Stavros Nikolopoulos, Leonidas Palios, and Charis Papadopoulos A Fully Dynamic Algorithm for the Recognition of P4-sparse Graphs
14:50-15:15 Liliana Alcon, Luerbio Faria, Celina Figueiredo, and Marisa Gutierrez Clique graph recognition is NP-complete
15:15-15:35 Coffee and cakes
16:00-20:00 Excursion to Hardanger Fjord. Boat leaves at 16:00 sharp!
20:30 Banquet

Saturday, June 24

09:00-09:25 Binh Minh Bui Xuan, Michel Habib, Limouzy Vincent, and Fabien de Montgolfier Homogeneity vs. Adjacency: generalising some graph decomposition algorithms
09:25-09:50 Haim Kaplan and Yahav Nussbaum Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
09:50-10:15 Jeremie Chalopin and Daniel Paulusma Graph labelings derived from models in distributed computing
10:15-10:40 Miklos Bartha and Miklos Kresz Flexible matchings
10:40-11:00 Coffee break
11:00-11:25 Elisabeth Gassner, Michael Juenger, Merijam Percan, Marcus Schaefer, and Michael Schulz Simultaneous Graph Embeddings with Fixed Edges
11:25-11:55 Bodo Manthey Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
11:55-12:20 Sylvain Coulonges Circular-Perfect Concave-Round Graphs
12:20-12:30 Closing of the conference
12:30-14:00 Lunch
Departure