WG 2007 Program

Wednesday, June 20, 2007
 16:00 - 20:00 Registration (Rosensäle, Fürstengraben 27))
Thursday, June 21, 2007
 08:00 - 08:30 Shuttle to Dornburg (8:00 "Hotel am Stadion" / 08:10 Jena bus station) 08:50 - 09:00 Welcome and Opening of WG 2007 09:00 - 09:50 Invited Talk: Ming-Yang Kao (Evanston, Illinois, USA) Algorithmic DNA Assembly 09:50 - 10:15 Petr Golovach and Jan Kratochvil Computational complexity of generalized domination: A complete dichotomy for chordal graphs 10:15 - 10:40 Arthur H. Busch and Garth Isaak Recognizing Bipartite Unbounded Tolerance Graphs in Linear Time 10:40 - 11:00 Coffee and tea break 11:00 - 11:25 David Richerby and Dimitrios M. Thilikos Graph Searching in a Crime Wave 11:25 - 11:50 Frédéric Mazoit and Nicolas Nisse Monotonicity of Non-deterministic Graph Searching 11:50 - 12:15 Vadim Lozin and Martin Milanic Tree-width and Optimization in Bounded Degree Graphs 12:15 - 12:40 Philippe Gambette and Stephane Vialette On restrictions of balanced 2-interval graphs 12:40 - 14:15 Lunch Break 14:15 - 14:40 Bruno Courcelle and Mamadou Moustapha Kanté Graph operations characterizing rank-width and balanced graph expressions 14:40 - 15:05 Frank Gurski and Egon Wanke The clique-width of tree-power and leaf-power graphs 15:05 - 15:30 Vincent Limouzy, Fabien de Montgolfier and Michaël Rao NLC-2 graph recognition and isomorphism 15:30 - 15:55 Daniel Meister A characterisation of the minimal triangulations of permutation graphs 15:55 - 16:15 Coffee and tea break 16:15 - 16:40 Maw-Shang Chang and Ming-Tat Ko The 3-Steiner Root Problem 16:40 - 17:05 U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski and D. Wagner On Finding Graph Clusterings with Maximum Modularity 17:05 - 17:30 Fabrizio Frati On Minimum Area Planar Upward Drawings of Directed Trees and Other Families of Directed Acyclic Graphs 17:30 - 17:55 Torben Hagerup A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs 18:30 - 19:15 Organ concert (Church in Dornburg) 19:30 - 19:50 Shuttle to Jena 20:00 - 21:00 Dinner (Zur Noll) 21:00 - 22:00 PC meeting
Friday, June 22, 2007
 08:00 - 08:30 Shuttle to Dornburg (8:00 "Hotel am Stadion" / 08:10 Jena bus station) 09:00 - 09:50 Invited Talk: Klaus Jansen (Kiel, Germany) Approximation algorithms for geometric intersection graphs 09:50 - 10:15 Angelo Monti, Paolo Penna and Riccardo Silvestri An Equivalent Version of the Caccetta-Haeggkvist Conjecture in an Online Load Balancing Problem 10:15 - 10:40 Luis Cereceda, Jan van den Heuvel and Matthew Johnson Mixing 3-Colourings in Bipartite Graphs 10:40 - 11:00 Coffee and tea break 11:00 - 11:25 Bodo Manthey Minimum-weight Cycle Covers and Their Approximability 11:25 - 11:50 Stefan Felsner and Florian Zickfeld On the number of $\alpha$-orientations 11:50 - 12:15 Bruno Escoffier, Laurent Gourves and Jerome Monnot Complexity and approximation results for the connected vertex cover problem 12:15 - 12:40 Peter Damaschke Segmenting Strings Homogeneously via Trees 12:40 - 14:15 Lunch Break 14:15 - 14:40 Van Bang Le and H.N. de Ridder Characterisations and linear-time recognition of probe cographs 14:40 - 15:05 Martin Pergel Recognition of Polygon-circle Graphs and Graphs of Interval Filaments is NP-complete 15:05 - 15:30 Min Chih Lin, Francisco Soulignac and Jayme L. Szwarcfiter Proper Helly Circular-Arc Graphs 15:30 - 15:50 Coffee and tea break 16:00 - 20:00 Excursion to Weimar 20:15 - 23:00 Conference dinner at Jena (Scala Restaurant)
Saturday, June 23, 2007
 08:00 - 08:30 Shuttle to Dornburg (8:00 "Hotel am Stadion" / 08:10 Jena bus station) 09:00 - 09:25 Karol Suchan and Ioan Todinca Pathwidth of circular-arc graphs 09:25 - 09:50 D. Meister, J.A. Telle and M. Vatshelle Characterization and recognition of digraphs of bounded Kelly-width 09:50 - 10:15 Frederic Dorn How to use planarity efficiently: new tree-decomposition based algorithms 10:15 - 10:40 Dániel Marx and Ildikó Schlotter Obtaining a Planar Graph by Vertex Deletion 10:40 - 11:00 Coffee and tea break 11:00 - 11:25 Fedor V. Fomin, Pinar Heggernes and Rodica Mihai Mixed search number and linear-width of interval and split graphs 11:25 - 11:50 Matthias Hagen Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation 11:50 - 12:15 Refael Hassin, Jerome Monnot and Danny Segev The Complexity of Bottleneck Labeled Graph Problems 12:15 - 12:25 Closing 12:25 - 14:00 Lunch 14:15 - 14:35 Shuttle to Jena