24rd International Workshop on

Graph-Theoretic Concepts in Computer Science (WG '98)

Smolenice-Castle/Slovakia, June 18 - 20, 1998

Preliminary Conference Program

Wednesday, 17 June 1998

16:00-20:00  Registration

16:15        Departure of the conference bus (or a car) 
             from the Bratislava airport

17:15        Departure of the conference bus from Bratislava bus station

17:45        Departure of the conference bus from Bratislava railway station

18:45        Expected arrival of the conference bus at the Smolenice Castle

20:00        Welcome party

Thursday, 18 June 1998

 8:30        Opening of the conference

 9:00-10:30  Session I 
             Chair: A. Brandstaedt

 9:00        Linear Time Solvable Optimization Problems on Certain
             Structured Graph Families 
             B. Courcelle, J. A. Makowsky, U. Rotics 

 9:30        Minus Domination in Small-Degree Graphs 
             P. Damaschke

10:00        The Vertex-Disjoint Triangles Problem
             V. Guruswami, C. P. Rangan, M.S. Chang, G.J. Chang, C.K. Wong 

10:30-11:00  Coffee Break

11:00-13:00  Session II
             Chair: P. Widmayer

11:00        Communication in the Two-way Listen-in Vertex-disjoint Paths Mode 
             H.-J. Boeckenhauer

11:30        Broadcasting on Anonymous Unoriented Torus
             S. Dobrev, P. Ruzicka

12:00        Families of Graphs having Broadcasting and Gossiping Properties
             G. Fertin, A. Raspaud 

12:30        Optical All-to-All Communication in Inflated Networks
             O. Togni

13:00-15:00  Lunch break

15:00-16:30  Session III
             Chair: H. Bodlaender

15:00        A generalization of AT-free graphs and a generic algorithm for
             solving treewidth, minimum fill-in and vertex ranking 
             H. Broersma, T. Kloks, D. Kratsch, H. Muller

15:30        A Polynomial-Time Algorithm for Finding Total Colorings of
             Partial k-Tress 
             S. Isobe, X. Zhou, T. Nishizeki

16:00        Ranking of Directed Graphs
             J. Kratochvil, Z. Tuza

16:30-17:00  Coffee break

17:00-19:00  Session IV
             Chair: D. Wagner

17:00        Drawing Planar Partitions II: HH-Drawings
             T. Biedl, M. Kaufmann, P. Mutzel

17:30        Triangles in Euclidean Arrangements
             S. Felsner, K. Kriegel

18:00        Internally Typed Second-Order Term Graphs
             W. Kahl

18:30        Almost Optimal Implicit Representation of Graphs
             M. Talamo, P. Vocca

19:00-20:00  Dinner

20:00        Meeting of the WG'98 program committee

Friday, 19 June 1998

 7:45- 8:30  Breakfast

 8:30-10:30  Session V
             Chair: R. Moehring

 8:30        Graphs with Bounded Induced Distance
             S. Cicerone, G. Di Stefano

 9:00        Diameter Determination on Restricted Graph Families
             D. G. Corneil, F. F. Dragan, M. Habib, C. Paul

 9:30        Independent Tree Spanners: Fault-Tolerant Spanning Trees with
             Constant Distance Guarantees 
             D. Handke

10:00        Upgrading Bottleneck Constrained Forests
             S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi,
             H. C. Wirth 

10:30-11:00  Coffee break

11:00-13:00  Session VI
             Chair: M. Nagl

11:00        Routing in Recursive Circulant Graphs: Edge Forwarding Index
             and Hamiltonian Decomposition 
             G. Guayacq, C. Micheneau, A. Raspaud 

11:30        Improved Compressions of Cube-Connected Cycles Networks
             R. Klasing

12:00        Efficient Embedding of Grids into Grids
             M. Rottger, U.-P. Schroeder

12:30        Integer Uniform Flows in Symmetric Networks
             F. Shahrokhi, L. A. Szekely

13:00-14:00  Lunch

14:00-17:00  Social events

17:30-18:50  Poster and demo session 
             Chair: L. Kucera
17:30        Deletion in Closure Spaces
             J. Pfaltz

17:45        On-line coloring of oriented graphs
             L. Vignal
18:00        Demonstration of HOPS (Visual programming with strongly Typed 
             Term Graphs)
             W. Kahl

18:30        Demonstration of shortest route calculations 
             U. Lauther 

19:30        Conference dinner (picnic like - outdoors - depends on the weather)

Saturday, 20 June 1998

 7:45-8:30   Breakfast
 8:30-10:30  Session VII
             Chair: M. Habib

 8:30        Splitting Number is NP-complete
             L. Faria, C. M. H. de Figueiredo, C. F. X. Mendonca

 9:00        Tree Spanners in Planar Graphs
             S. P. Fekete, J. Kremer

 9:30        A Linear-Time Algorithm to Find Four Independent Spanning Trees
             in Four-Connected Planar Graphs 
             K. Miura, D. Takahashi, S. Nakano, T. Nishizeki 

10:00        Linear Algorithms for a k-partition Problem of Planar Graphs
             without Specifying Bases 
             K. Wada, W. Chen

10:30-11:00  Coffee break

11:00-13:00  Session VIII
             Chair: G. Tinhofer

11:00        Domination and Steiner Tree Problems on Graphs with Few P_4s
             L. Babel, S. Olariu 

11:30        Minimum Fill-in and Treewidth for Graphs Modularly Decomposable
             into Chordal Graphs 
             E. Dahlhaus

12:00        Interval completion with the smallest max-degree 
             F. V. Fomin, P. A. Golovach

12:30        An estimate of the tree-width of a graph which has not a given
             planar grid as a minor 
             K. Y. Gorbunov

13:00-14:00  Lunch

14:00        Expected departure of the conference bus from the Smolenice Castle