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