Skip to main content Skip to navigation

AGT 2009 - Program

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
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é
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
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
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
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
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