Monday 23 March 2009
8:30 – 8:55	Registration. Warwick Mathematics Institute
8:55 – 9:00	Opening
Invited Session. Room MS.01
9:00 – 10:00	Bruno Courcelle LaBRI	Short vertex labels for connectivity checking in planar graphs with forbidden parts
10:00 – 10:30	Coffee break
Morning Session. Room MS.01
10:30 – 10:55	Mamadou Moustapha Kanté LaBRI	Short Labeling Scheme for Connectivity Check on Certain Graph Classes of Unbounded Clique-Width
10:55 – 11:20	Pinar Heggernes, Daniel Meister and Charis Papadopoulos University of Bergen	A new representation of proper interval graphs with an application to clique-width
11:20 – 11:45	Robert Ganian and Petr Hlineny Masaryk University	On Parse Trees and Myhill-Nerode-type Tools for handling Graphs of Bounded Rank-width
11:45 – 12:10	Binh-Minh Bui-Xuan, Jan Arne Telle and Martin Vatshelle University of Bergen	Dynamic programming on graph of bounded rank-width in fast FPT time using unions of neighbourhoods
12:10 – 14:00	Lunch (Radcliffe House)
Early Afternoon Session. Room MS.01
14:00 – 14:25	Carmen Centeno, Mitre Dourado and Jayme Szwarcfiter Universidade Federal do Rio de Janeiro	On the convexity of paths of length two in undirected graphs
14:25 – 14:50	Gregory Gutin Royal Holloway, University of London	Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems
14:50 – 15:15	Stephan Kreutzer and Anuj Dawar University of Oxford and University of Cambridge Computer Laboratory	Dominating Sets in Nowhere Dense Classes of Structures
15:15 – 15:40	Ferdinando Cicalese and Martin Milanic Universität Bielefeld	The structure of graphs of separability at most 2
15:40 – 16:10	Coffee break
Late Afternoon Session. Room MS.01
16:10 – 16:35	Daniel Brügmann, Christian Komusiewicz and Hannes Moser Friedrich-Schiller-Universität Jena	On Generating Triangle-Free Graphs
16:35 – 17:00	Kathie Cameron, Chinh Hoang and Benjamin Leveque Wilfrid Laurier University	Asteroids in rooted and directed path graphs
17:00 – 17:25	Domingos Cardoso and Sofia Pinheiro Universidade de Aveiro	Spectral upper bounds on the size of k-regular induced subgraphs
17:25 – 17:50	Marcin Kaminski, Pim van’t Hof and Daniël Paulusma University of Durham and Université Libre de Bruxelles	Induced paths with parity constraints in claw-free graphs
Tuesday 24 March 2009
Invited Session. Room MS.01
9:00 – 10:00	Rolf Niedermeier Friedrich-Schiller-Universität Jena	Some Models for Graph-Based Data Clustering
10:00 – 10:30	Coffee break
Morning Session. Room MS.01
10:30 – 10:55	Alexander Grigoriev, Natalya Usotskaya and Bert Marchal Maastricht University	On planar graphs with large tree-width and small grid minors
10:55 – 11:20	Ignasi Sau and Dimitrios Thilikos UPC, Barcelona and NKUA, Athens	Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs
11:20 – 11:45	Frédéric Mazoit LaBRI	Tree-width of graphs and surface duality
11:45 – 12:10	Hans L. Bodlaender, Stéphan Thomassé and Anders Yeo Universiteit Utrecht, LIRMM Montpellier and Royal Holloway, University of London	Analysis of Data Reduction: Transformations give evidence for non-existence of polynomial kernels
12:10 – 13:30	Lunch (Common Room)
Early Afternoon Session. Room MS.01
13:30 – 13:55	Stan van Hoesel and Bert Marchal Maastricht University	Finding good tree decompositions by local search
13:55 – 14:20	Illya Hicks Rice University	Integer Programming Techniques for General Branchwidth
14:20 – 14:45	Andras Salamon University of Oxford	Multicoloured cliques in vertex-coloured graphs
14:45 – 15:00	Coffee break
Mid Afternoon Session. Room MS.01
15:00 – 15:25	Vladimir Deineko and Alexander Tiskin DIMAP, University of Warwick	Minimum-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio
15:25 – 15:50	David Coudert, Dorian Mazauric and Nicolas Nisse INRIA, Sophia-Antipolis	On Rerouting Connection Requests in Networks with Shared Bandwidth
15:50 – 16:15	Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff and Alexander Wolff University of Leicester, Universität Augsburg, Universität Kiel, TU-Berlin and TU-Eindhoven	Trimming of Graphs, with Applications to Point Labeling
16:15 – 16:40	P. Tittmann, I. Averbouch and J.A. Makowsky Technion	The Enumeration of Vertex Induced Subgraphs with respect to the Number of Components
17:00 – 19:00	Excursion to Coventry Transport Museum
19:30 – 23:00	Dinner at St. Mary's Guildhall
Wednesday 25 March 2009
Invited Session. Room MS.01
9:00 – 10:00	Martin Golumbic University of Haifa	Conflict and Tolerance in Algorithmic Graph Theory
10:00 – 10:30	Coffee break
Morning Session. Room MS.01
10:30 – 10:55	Michel Habib and Juraj Stacho LIAFA	Linear Algorithms for Chordal Graphs of Bounded Directed Vertex Leafage
10:55 – 11:20	Michel Habib and Vincent Limouzy LIAFA and University of Toronto	On some simplicial elimination schemes for chordal graphs
11:20 – 11:45	Kristina Vuskovic and Nicolas Trotignon University of Leeds and LIAFA	Graphs with no cycle with a unique chord
11:45 – 12:10	Christophe Paul, E. Gioan, M. Tedder and D. Corneil Laboratoire d'Informatique Robotique et Microélectronique de Montpellier	A new quasi-linear time split decomposition algorithm
12:10 – 14:00	Lunch (Radcliffe House)
Early Afternoon Session. Room MS.01
14:00 – 14:25	Feodor Dragan, Yang Xiang and Chenyu Yan Kent State University	Collective Tree Spanners for Unit Disk Graphs with Applications
14:25 – 14:50	Leo van Iersel and Matthias Mnich Technische Universiteit Eindhoven	Rooted and Unrooted Maximum Consistent Supertrees
14:50 – 15:15	Enide Martins, Liliana Costa and Carlos Fonseca Universidade de Aveiro	Counting vertices and edges of a Birkhoff polytope for trees
15:15 – 15:40	Pierre Charbit, Fabien de Montgolfier and Mathieu Raffinot LIAFA	On split decomposition of undirected graph
15:40 – 16:10	Coffee break
Late Afternoon Session. Room MS.01
16:10 – 16:35	Nicholas Korpelainen DIMAP, University of Warwick	A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs
16:35 – 17:00	Stanislav Živný, David Cohen and Peter Jeavons University of Oxford	The Expressive Power of Binary Submodular Functions
17:00 – 17:25	Andreas Brandstadt and Raffaele Mosca Universität Rostock and Universita' degli Studi "G. d'Annunzio"	On Variants of the Maximum Induced Matching Problem
17:25 – 17:50	Tomas Feder, Pavol Hell, Jing Huang and Arash Rafiey Simon Fraser University and University of Victoria	Adjusted Interval Digraphs