Graph-Theoretic Concepts in Computer Science: International Workshop WG ’87 Kloster Banz/Staffelstein, FRG, June 29 – July 1, 1987 Proceedings

Hartmut Ehrig, Paul Boehm, Udo- Hummert (auth.), Herbert Göttler, Hana-Jürgen Schneider (eds.)3540194223, 9783540194224

This book reflects the scientific program of the annual workshop on Graph-theoretic Concepts in Computer Science in 1987. The purpose of this conference is to be the “missing link” between theory and application of graphs in as many branches of computer science as a conference scheduled for three days without parallel sessions can permit. So the organizers of WG ’87 addressed a selected group of people with a strong interest in theory and practice. The proceedings include latest results on “classical” graph-theoretic problems (including formal language theory applied to graphs) and how to apply those results to practical problems, e.g. data bases, layout of graph operating systems, software engineering, chemistry, and modelling with graphs.

---

Table of contents :
Distributed parallelism of graph transformations….Pages 1-19
A PrT-net representation of graph grammars….Pages 20-31
Pretty patterns produced by hyperedge replacement….Pages 32-45
Graph languages defined by systems of forbidden structures: A survey….Pages 46-58
A sweepcircle algorithm for Voronoi diagrams….Pages 59-69
Competitive location in the L 1 and L inf metrics….Pages 70-83
Priority search trees in secondary memory (extended abstract)….Pages 84-93
On the analysis of grid structures for spatial objects of non-zero size….Pages 94-105
Maintenance of transitive closures and transitive reductions of graphs….Pages 106-120
Upward drawings of acyclic digraphs….Pages 121-133
Approximate counting, uniform generation and rapidly mixing markov chains extended abstract….Pages 134-148
On chaotic behaviour of some np-complete problems….Pages 149-161
External labeling and algorithms for hierarchic networks….Pages 162-170
Designing gamma-acyclic database schemes using decomposition and augmentation techniques….Pages 171-185
Graph-theoretical tools and their use in a practical distributed operating system design case….Pages 186-205
Development of several reachability algorithms for directed graphs….Pages 206-218
On integration mechanisms within a graph-based software development environment….Pages 219-229
Restructuring aspect graphs into aspect- and cell-equivalence classes for use in computer vision….Pages 230-241
Automatic crystal chemical classification of silicates using direction-labeled graphs….Pages 242-254