17. WG 1991: Fischbachau, Germany

Tree-Related Problems

• Hans L. Bodlaender, John R. Gilbert, Ton Kloks, Hjálmtyr Hafsteinsson:
  Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height. 1-12
  
• Bruno Courcelle, Mohamed Mosbah:
  Monadic Second-Order Evaluations on Tree-Decomposable Graphs. 13-24
  
• Ralf Heckmann, Ralf Klasing, Burkhard Monien, Walter Unger:
  Optimal Embedding of Complete Binary Trees into Lines and Grids. 25-35
  

Graph Grammars and Rewriting

• Yasuyoshi Okada, Masahiro Hayashi:
  Graph Rewriting Systems and their Application to Network Reliability Analysis. 36-47
  
• Albert Zündorf, Andy Schürr:
  Nondeterministic Control Structures for Graph Rewriting Systems. 48-62
  
• Marc Andries, Jan Paredaens:
  A Language for Generic Graph-Transformations. 63-74
  
• Rudolf Freund, Brigitte Haberstroh:
  Attributed Elementarz Programmed Graph Grammars. 75-84
  

Complexity

• Edmund Ihler:
  The Complexity of Approximating the Class Steiner Tree Problem. 85-96
  
• Zbigniew Lonc:
  On Complexity of Some Chain and Antichain Partition Problems. 97-104
  

Computational Geometry

• Jurek Czyzowicz, Eduardo Rivera-Campo, Nicola Santoro, Jorge Urrutia, Joseph Zaks:
  Tight Bounds for the Rectangualr Art Gallery Problem. 105-112
  
• Leonidas J. Guibas, Joseph S. B. Mitchell:
  Voronoi Diagrams of Moving Points in the Plane. 113-125
  

Parallel Algorithms

• Takayoshi Shoudai:
  Using Maximal Independent Sets to Solve Problems in Parallel. 126-134
  
• Zvi M. Kedem, Krishna V. Palem, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis:
  Fast Parallel Algorithms for Coloring Random Graphs. 135-147
  

Complexity Problems and Others

• Xiaoyi Jiang, Horst Bunke:
  Optimal Vertex Ordering of a Graph and its Application to Symmetry Detection. 148-158
  
• Ondrej Sýkora, Imrich Vrto:
  Edge Separators for Graphs of Bounded Genus with Applications. 159-168
  
• Ding-Zhu Du, Yuh-Dauh Lyuu, D. Frank Hsu:
  Line Digraph Iterations and Spread Concept - with Application to Graph Theory, Fault Tolerance, and Routing. 169-179
  
• Ludek Kucera:
  A Generalized Encryption Scheme Based on Random Graphs. 180-186
  

Path-Oriented Algorithms

• Esteban Feuerstein, Alberto Marchetti-Spaccamela:
  Dynamic Algorithms for Shortest Paths in Planar Graphs. 187-197
  
• Iain A. Stewart:
  Copmlete Problems for Logspace Involving Lexicographic First Paths in Graphs. 198-208
  
• Tadao Takaoka:
  A New Upper Bound on the Complexity of the All Pairs Shortest Path Problem. 209-213
  

Applications to VLSI

• Ondrej Sýkora, Imrich Vrto:
  On the Crossing Number of the Hypercube and the Cube Connected Cycles. 214-218
  
• Peter Damaschke:
  Logic Arrays for Interval Indicator Functions. 219-225
  
• Elena Stöhr:
  On the Broadcast Time of the Butterfly network. 226-229
  

Disjoint Cycle Problems

• Hans L. Bodlaender:
  On Disjoint Cycles. 230-238
  
• Andreas Brandstädt:
  Short Disjoint Cycles in Cubic Bridgeless Graphs. 239-249