18. WG 1992: Wiesbaden-Naurod, Germany

Restricted Graph Classes

• Andreas Brandstädt:
  On Improved Time Bounds for Permutation Graph Problems. 1-10
  
• Wen-Lian Hsu:
  A Simple Test for Interval Graphs. 11-16
  
• Stefan Felsner:
  Tolerance Graphs and Orders. 17-26
  

Scheduling and Related Problems

• Klaus Jansen:
  On Scheduling Problems Restricted to Interval Orders. 27-36
  
• Hans L. Bodlaender, Klaus Jansen, Gerhard J. Woeginger:
  Scheduling with Incompatible Jobs. 37-49
  
• Klaus Jansen, Petra Scheffler:
  Generalized Coloring for Tree-like Graphs. 50-59
  

Parallel and Distributed Algorithms I

• Elias Dahlhaus:
  Optimal (Parallel) Algorithms for the All-to-All Vertices Distance Problem for Certain Graph Classes. 60-69
  
• Juraj Hromkovic:
  Topology of Parallel Networks and Computational Complexity (Extended Abstract). 70-77
  
• W. Preilowski:
  Parallel Triangulation of Nonconvex Polytopes. 78-89
  

Combinatorial Graph Problems I

• Hans L. Bodlaender:
  Kayles on Special Classes of Graphs - An Application of Sprague-Grundy Theory. 90-102
  
• Jianer Chen:
  A Linear Time Algorithm for Isomorphism of Graphs of Bounded Average Genus. 103-113
  
• Dinesh Bhatia, Frank Thomson Leighton, Fillia Makedon, Carolyn Haibt Norton:
  Improved Algorithms for Routing on Two-Dimensional Grids. 114-122
  
• Edmund Ihler:
  Minimum Rectilinear Steiner Tree for Intervals on two Parallel Lines. 123-134
  

Parallel and Distributed Algorithms II

• Ornan Ori Gerstel, Shmuel Zaks:
  A New Characterization of Tree Medians with Applications to Distributed Algorithms. 135-144
  

Graph Decomposition

• Yefim Dinitz:
  The 3-Edge-Components and a Structural Description of All 3-Edge-Cuts in a Graph. 145-157
  
• Jianer Chen, Arkady Kanevsky:
  On Assembly of Four-Connected Graphs (Extended Abstract). 158-169
  
• Beverly Jamison, Stephan Olariu:
  On the Homogeneous Decomposition of Graphs. 170-183
  

Combinatorial Graph Problems II

• Sajal K. Das, Aisheng Mao:
  Embeddings in Recursive Combinatorial Networks. 184-204
  
• Mikkel Thorup:
  On Shortcutting Digraphs. 205-211
  
• Alain Cournier, Michel Habib:
  An Efficient Algorithm to Recognize Prime Undirected Graphs. 212-224
  
• Stefan Felsner, Dorothea Wagner:
  On the Complexity of Partial Order Properties. 225-235
  

Graph Grammars and Geometry

• Mohamed Mosbah:
  Probabilistic Graph Grammars. 236-247
  
• Francesco Parisi-Presicce:
  Single vs. Double Pushout Derivations of Graphs. 248-262
  
• Goos Kant:
  Hexagonal Grid Drawings. 263-276
  

Modelling by Graphs

• Martin Erwig:
  Graph Algorithms = Iteration + Data Structures? The Structure of Graph Algorithms and a Corresponding Style of Programming. 277-292
  
• Paola Alimonti, Esteban Feuerstein:
  Petri Nets, Hypergraphs and Conflicts (Preliminary Version). 293-309
  
• Jordan Gergov, Christoph Meinel:
  Analysis and Manipulation of Boolean Functions in Terms of Decision Graphs. 310-320
  
• Una-May O'Reilly, Nicola Santoro:
  The Expressiveness of Silence: Tight Bounds for Synchronous Communication of Information Using Bits and Silence. 321-332
  
• Igor Litovsky, Yves Métivier, Wieslaw Zielonka:
  The Power and the Limitations of Local Computations on Graphs. 333-345