View WG 2010 calendar (updated online) Transfer Information Program of WG 2010Sunday, 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 |