View WG 2010 calendar (updated online)
Transfer Information

Program of WG 2010

Sunday, June 27


18:00 - 20:15    Registration opens
20:15 - 22:30    Welcome reception



Monday, June 28


08:45 - 09:00    Opening
09:00 - 10:00    Invited Talk of Dimitris Achlioptas: Algorithmic Barriers from Phase Transitions in Graphs

09:00    Break

1st Session  (Chair: Fedor Fomin)

10:15 - 10:40   Yota Otachi, Hans L. Bodlaender and Erik Jan van Leeuwen. 
                        Complexity Results for the Spanning Tree Congestion Problem    
10:40 - 11:05   Marcin Kaminski.
                        Max-Cut and containment relations in graphs
11:05 - 11:30   Stavros Nikolopoulos and Kyriaki Ioannidou.
                        The Longest Path Problem is Polynomial on Cocomparability Graphs
11:30 - 11:55   Petr Golovach, Dieter Kratsch and Jean-Francois Couturier.
                        Colorings With Few Colors: Counting, Enumeration and Combinatorial Bounds

11:55 - 12:10    Break

2nd Session (Chair: Ingo Schiermeyer)

12:10 - 12:35    Tamas Fleiner.
                         On stable matchings and flows
12:35 - 13:00    Hajo Broersma, Petr Golovach, Daniel Paulusma and Jian Song.
                         Narrowing down the gap on the complexity of coloring P_k-free graphs
13:00 - 13:25    Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov and Jesper Nederlof.
                         Computing the cutwidth of bipartite permutation graphs in linear time

14:00 - 15:00    Lunch

3rd Session (Chair: Haiko Müller)

16:00 - 16:25    Mathieu Liedloff, Ioan Todinca and Yngve Villanger.
                         Solving Capacitated Dominating Set by using Covering by Subsets and Maximum Matching
16:25 - 16:50    Frederic Dorn, Hannes Moser, Rolf Niedermeier and Mathias Weller.
                         Efficient Algorithms for Eulerian Extension
16:50 - 17:15    Ge Xia and Yong Zhang.
                         On the Small Cycle Transversal of Planar Graphs

17:15 - 17:30    Break

4th Session (Chair: Dieter Kratsch)

17:30 - 17:55    Panos Giannopoulos, Christian Knauer, Mike Fellows, Christophe Paul, Frances Rosamond, Sue Whitesides and Nathan Yu.
                         Milling a Graph with Turn Costs: a Parameterized Complexity Perspective
17:55 - 18:20    Karin Arikushi, Radoslav Fulek, Balazs Keszegh, Filip Moric and Csaba Toth.
                         Drawing Graphs with Orthogonal Crossings
18:20 - 18:45    Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk and Jakub Wojtaszczyk.
                         Kernelization hardness of connectivity problems in d-degenerate graphs

18:45 - 20:15    Steering Committee Meeting

20:15 - 22:30    Dinner



Tuesday, June 29


09:00 - 10:00    Invited Talk of Erik Demaine: Algorithmic Graph Minors and Bidimensionality

09:00    Break

5th Session (Chair: Martin Golumbic)

10:15 - 10:40   Isolde Adler, Binh-Minh Bui-Xuan, Yuri Rabinovich, Gabriel Renault, Jan Arne Telle and Martin Vatshelle.
                        On the boolean-width of a graph: structure and applications
10:40 - 11:00   Pinar Heggernes, Daniel Lokshtanov, Jesper Nederlof, Christophe Paul and Jan Arne Telle.
                        Generalized graph clustering: recognizing (p,q)-cluster graphs
11:00 - 11:30   Konrad Dabrowski, Vadim Lozin, Rajiv Raman and Bernard Ries.
                        Colouring vertices of triangle-free graphs
11:30 - 11:55   Geevarghese Philip, Venkatesh Raman and Yngve Villanger.
                        A Quartic Kernel for Pathwidth-One Vertex Deletion

11:55 - 12:10    Break

6th Session (Chair: Hans Bodlaender)

12:10 - 12:35    Jeremie Chalopin, Paola Flocchini, Bernard Mans and Nicola Santoro.
                         Network Exploration  by Silent and Oblivious Robots
12:35 - 13:00    Annabell Berger and Matthias Müller-Hannemann.
                         Uniform Sampling of Undirected and Directed Graphs with a Fixed Degree Sequence
13:00 - 13:25    René van Bevern, Christian Komusiewicz, Hannes Moser and Rolf Niedermeier.
                         Measuring Indifference: Unit Interval Vertex Deletion

14:00 - 15:00    Lunch

16:20 - 20:00    Excursion: Faistos Palace -  Archaeological site (1 hour tour), Matala Beach (1+1/2 hour aprox. time to swim)

20:15 - 22:30    Dinner: Domain Zacharioudakis



Wednesday, June 30


7th Session (Chair: Mike Fellows)

09:30 - 09:55    Dániel Marx and Ildikó Schlotter.
                         Parameterized Complexity of the Arc-Preserving Subsequence Problem
09:55 - 10:20    Steven Chaplick, Marisa Gutierrez, Benjamin Lévêque and Silvia Tondato.
                         From path graphs to directed path graphs
10:20 - 10:45    Nicolas Bonichon, Cyril Gavoille, nicolas hanusse and David Ilcinkas.
                         Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
10:45 - 11:10    Robert Elsaesser and Adrian Ogierman. Efficient Broadcasting in Random Power Law Networks

11:10 - 11:30    Break

8th Session (Chair: TBA )

11:30 - 11:55    Padmini Mukkamala, Janos Pach and Deniz Sarioz.
                        Graphs with large obstacle numbers 
11:55 - 12:20    Edyta Szymanska.
                        The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Codegree
12:20 - 12:45   Colin McDiarmid and Tobias Mueller.
                        The number of bits needed to represent a unit disk graph
12:45 - 13:15   Jannik Matuschke and Britta Peis.
                        Lattices and maximum flow algorithms in planar graphs

14:00 - 15:00   Lunch