WG 2000 Program
Konstanz, Germany, June 15-17, 2000
WEDNESDAY, June 14, 2000
- Registration
- The registration office is open throughout the afternoon.
- 19:00 Reception
THURSDAY, June 15, 2000
- 09:00 Frank Gurski and Egon Wanke
- The Tree-Width of Clique-Width Bounded Graphs Without Kn,n
- 09:25 Fedor Fomin, Dieter Kratsch and Haiko Müller
- On the Domination Search Number
- 09:50 Peter Damaschke
- Efficient Dispersion Algorithms For Geometric Intersection Graphs
10:15 Coffee Break
- 10:45 Luisa Gargano, Andrzej Pelc, Stephane Perennes and Ugo Vaccaro
- Efficient Communication in Unknown Networks
- 11:10 Jean-Michel Hélary and Giovanna Melideo
- Minimal Size of Piggybacked Information for Tracking Causality: A Graph-Based Characterization
- 11:35 Michael J. Dinneen and Bakhadyr Khoussainov
- Update Networks and Their Routing Strategies
12:00 Lunch Break
- 14:30 Gianfranco Bilardi, Andrea Pietracaprina and Paolo D'Alberto
- On the Space and Access Complexity of Computation DAGs
- 14:55 Andreas Jakoby, Maciej Liskiewicz and Rüdiger Reischuk
- The Expressive Power and Complexity of Dynamic Process Graphs
- 15:20 Sergei L. Bezrukov, Robert Elsässer, Burkhard Monien, Robert Preis and Jean-Pierre Tillich
- New Spectral Lower Bounds on the Bisection Width of Graphs
15:45 Coffee Break
- 16:15 Ton Kloks, Dieter Kratsch, Yvan Le Borgne and Haiko Müller
- Bandwidth of Split and Circular Permutation Graphs
- 16:40 Andreas Brandstädt and Van Bang Le
- Split-Perfect Graphs: Characterizations and Algorithmic Use
- 17:05 Ekkehard G. Köhler
- Recognizing Graphs without Asteroidal Triples
- 17:30 Vincent Bouchitté and Ioan Todinca
- Approximating the Treewidth of AT-free Graphs
18:30 Dinner
- 20:00 PC Meeting
FRIDAY, June 16, 2000
- 09:00 Invited Lecture: Emo Welzl
- n Points and One Line: Analysis of Randomized Games
10:00 Short Break
- 10:15 Edson Cáceres, Albert Chan, Frank Dehne and Giuseppe Prencipe
- Coarse Grained Parallel Algorithms for Detecting Convex Bipartite Graphs
- 10:40 Assefaw Hadish Gebremedhin, Isabelle Guérin Lassous, Jens Gustedt and Jan Arne Telle
- Graph Coloring on a Coarse Grained Multiprocessor
11:05 Coffee Break
- 11:30 Ingo Demgensky, Hartmut Noltemeier and Hans-Christoph Wirth
- Optimizing Cost Flows by Modifying Arc Costs and Capacities
- 11:55 Goran Konjevod, Sven O. Krumke and Madhav Marathe
- Budget Constrained Minimum Cost Connected Medians
- 12:20 Sandeep Bhatt, Shimon Even, David Greenberg and Rafi Tayar
- Traversing Directed Eulerian Mazes
12:45 Lunch Break
- 14:30 Departure by boat from near Waldhaus Jakob for the
- Excursion on Lake Constance (Bodensee) and Conference Dinner
SATURDAY, June 17, 2000
- 09:00 Invited Lecture: Ingo Wegener
- On the Expected Runtime and the Success Probability of Evolutionary Algorithms
10:00 Short Break
- 10:15 Guillaume Fertin, André Raspaud, Heiko Schröder, Ondrej Sýkora and Imrich Vrto
- Diameter of the Knödel Graph
- 10:40 Jan Kratochvíl, Andrzej Proskurowski and Heinz-Jürgen Voss
- Coloring Mixed Hypertrees
11:05 Coffee Break
- 11:30 Stefan Dobrev
- Computing Input Multiplicity in Anonymous Synchronous Networks with Dynamic Faults
- 11:55 Koichi Wada and Wei Chen
- Optimal Fault-Tolerant Routings for k-connected Graphs with Smaller Routing Tables
- 12:20 Luca Becchetti, Miriam Di Ianni and Alberto Marchetti-Spaccamela
- Approximating Call-Scheduling Makespan in All-Optical Networks
12:45 Lunch Break
- 14:15 Serafino Cicerone and Gabriele Di Stefano
- Networks with Small Stretch Number
- 14:40 Dagmar Handke and Guy Kortsarz
- Tree Spanners for Subgraphs and Related Tree Covering Problems
- 15:05 Sayaka Nagai and Shin-ichi Nakano
- A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs
15:30 End of Workshop