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:00 | Lunch 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 |
|