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 |