Graph-Theoretic Concepts in Computer Science: International Workshop WG ’86 Bernried, Federal Republic of Germany, June 17–19, 1986 Proceedings

Norbert Korte, Rolf H. Möhring (auth.), Gottfried Tinhofer, Gunther Schmidt (eds.)3540172181, 9783540172185

Graph-theoretic concepts are developed by computer scientists in order to model algorithms, nets, rewriting systems, distributed systems, parallelism, geometric and layout concepts. Their complexity is studied under various randomness assumptions. This volume contains contributions to the twelfth of a series of annual workshops designed to bring together researchers using graph-theoretic methods. Its purpose is to broadcast emerging new developments from and to a diversity of application fields. The topics covered include: Graph Grammars, Graph Manipulation, Nets, Complexity Issues, Algorithmic and Network Considerations, Outerplanar Graphs, Graph Isomorphism, Parallelism and Distributed Systems, Graphs and Geometry, Randomness Considerations, Applications in Chemistry, Specific Algorithms. N

---

Table of contents :
A simple linear-time algorithm to recognize interval graphs….Pages 1-16
On approximation algorithms for Steiner’s problem in graphs….Pages 17-28
Specification of error distances for graphs by precedence graph grammars and fast recognition of similarity….Pages 29-40
ADA concurrency specified by graph grammars….Pages 41-57
Cabri, an interactive system for graph manipulation….Pages 58-67
An interactive graphical manipulation system for higher objects based on relational algebra….Pages 68-81
Behaviour preserving refinements of Petri nets….Pages 82-93
The bandwidth of planar distributive lattices….Pages 94-105
The node visit cost of brother trees….Pages 106-117
Searching connected components in very large grid graphs….Pages 118-130
A simple implementation of Warshall’s algorithm on a vlsi chip….Pages 131-145
On some generalizations of outerplanar graphs: Results and open problems….Pages 146-164
Recognizing outerplanar graphs in linear time….Pages 165-176
Graphs and graph polynomials of interest in chemistry….Pages 177-187
Applications of parallel scheduling to perfect graphs….Pages 188-203
A graph-theoretic approach for designing fair distributed resource scheduling algorithms….Pages 204-226
Improved diameter bounds for altered graphs….Pages 227-236
Separability of sets of polygons….Pages 237-251
Centipede graphs and visibility on a cylinder….Pages 252-263
The diameter of connected components of random graphs….Pages 264-276
An algorithm for testing planarity of hierarchical graphs….Pages 277-289
EDM — A data model for electronic CAD/CAM-applications….Pages 290-305