18. WG 1992: Wiesbaden-Naurod, Germany

Ernst W. Mayr (Ed.): Graph-Theoretic Concepts in Computer Science, 18th International Workshop, WG '92, Wiesbaden-Naurod, Germany, June 19-20, 1992, Proceedings. Lecture Notes in Computer Science 657 Springer 1993, ISBN 3-540-56402-0 BibTeX

Restricted Graph Classes

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

Scheduling and Related Problems

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

Parallel and Distributed Algorithms I

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

Combinatorial Graph Problems I

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

Parallel and Distributed Algorithms II

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

Graph Decomposition

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

Combinatorial Graph Problems II

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

Graph Grammars and Geometry

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

Modelling by Graphs

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