University of Rostock, Department of Computer Science, Institute of Theoretical Computer Science

WG 2001 Program

WEDNESDAY, June 13, 2001

18:00 Reception
The registration office is open from 18:00 till 20:00.

THURSDAY, June 14, 2001

09:00 C. Gröpl, S. Hougardy, T. Nierhoff, H.J. Prömel
Lower Bounds for Approximation Algorithms for the Steiner Tree Problem

09:25 Fedor V. Fomin and Hans L. Bodlaender
Approximation of pathwidth of outerplanar graphs

09:50 Ioannis Caragiannis et al.
Approximate Constrained Bipartite Edge Coloring

10:15 Coffee Break

10:45 Derek G. Corneil and Udi Rotics
On the relationship between clique-width and treewidth

11:10 Wolfgang Espelage, Frank Gurski, Egon Wanke
How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time

11:35 Öjvind Johansson
log $n$-Approximative $NLC_k$-Decomposition in $O(n^{2k+1})$ Time

12:00 Lunch Break

14:30 Ekkehard Köhler, Derek G. Corneil, Stephan Olariu, Lorna Stewart
On Subfamilies of AT-free Graphs

14:55 Feodor F. Dragan
Estimating All Pairs Shortest Paths in Restricted Graph Families: An Unified Approach

15:20 Annegret Wagler
Critical and Anticritical Edges in Perfect Graphs

15:45 Coffee Break

16:15 R. Pendavingh, P. Schuurman, G.J. Woeginger
De Bruijn graphs and DNA graphs

16:40 Sven Fuhrmann, Sven Oliver Krumke, Hans-Christoph Wirth
Multiple Hotlink Assignment

17:05 Sergei L. Bezrukov and Robert Elsässer
Edge-Isoperimetric Problems for Cartesian Powers of Regular Graphs

17:30 Eunseuk Oh and Jianer Chen
On Strong Menger-Connectivity of Star Graphs

18:30 Dinner

20:00 PC Meeting

FRIDAY, June 15, 2001

09:00 Invited Lecture: H.-J. Bandelt (Hamburg)
Median hulls as Steiner hulls in rectilinear and molecular sequence spaces

10:00 Short Break

10:15 Sabine Cornelsen, Yefim Dinitz and Dorothea Wagner
Planarity of the 2-level Cactus Model

10:40 Antonio Puricella and Iain A. Stewart
A generic greedy algorithm, partially-ordered graphs and NP-completeness

11:05 Coffee Break

11:30 D. Král, J. Kratochvíl, Zs. Tuza, G. Woeginger
Complexity of coloring graphs without forbidden induced subgraphs

11:55 G. Fertin, A. Raspaud, B. Reed
On Star Coloring of Graphs

12:20 J. Fiala, K. Jansen, V. B. Le, E. Seidel
Graph Subcolorings: Complexity and Algorithms

12:45 Lunch Break

14:30 Excursion and Conference Dinner

SATURDAY, June 16, 2001

09:00 Invited Lecture: F. Meyer auf der Heide
Data Management in Networks

10:00 Short Break

10:15 Maurizio Patrignani and Maurizio Pizzonia
The Complexity of the Matching-Cut Problem

10:40 Van Bang Le, Bert Randerath
On stable cutsets in line graphs

11:05 Coffee Break

11:30 Fedor V. Fomin and Dimitros M. Thilikos
On the Monotonicity of Games Generated by Connectivity Functions

11:55 Maw-Shang Chang, T. Kloks and C. -M. Lee
Maximum clique transversals

12:20 Maw-Shang Chang and Haiko Müller
On the tree-degree of graphs

12:45 Lunch Break

14:15 Cyril Gavoille, David Peleg, André Raspaud and Eric Sopéna
Small $k$-Dominating Sets in Planar Graphs with Applications

14:40 Jianer Chen and Iyad A. Kanj
On Constrained Minimum Vertex Covers of Bipartite Graphs: Improved Algorithms

15:05 Serafino Cicerone, Gianluca D'Ermiliis, Gabriele Di Stefano
$(k,+)$-Distance-Hereditary Graphs

15:30 Haodi Feng
$(g, f)$-Factorizations Orthogonal to $k$ Subgraphs

15:55 End of Workshop
Back to the WG 2001 Home Page.
University of Rostock - Department of Computer Science - Institute of Theoretical Computer Science
wg2001@informatik.uni-rostock.de

Last modified: April 20th, 2001. 2293 accesses on this page since Dezember 5, 2003.