Graph-Theoretic Concepts in Computer Science: International Workshop WG ’88 Amsterdam, The Netherlands, June 15–17, 1988 Proceedings

Hans L. Bodlaender (auth.), J. van Leeuwen (eds.)3540507280, 9783540507284

This volume presents the proceedings of the 14th International Workshop on Graph-Theoretic Concepts in Computer Science (WG ’88), held from June 15 to 17, 1988 in Amsterdam, The Netherlands. It contains 31 papers on new or current developments in the area of graph-based algorithms. The topics covered include e.g. structural graph theory, parallel graph algorithms, graph-based modeling (in database theory and VLSI), computational geometry and applied graph theory. The book contains the revised versions of all the papers presented at the workshop. The revisions are based on comments and suggestions received by the authors during and after the workshop.

---

Table of contents :
NC-algorithms for graphs with small treewidth….Pages 1-10
Graph-theoretic properties compatible with graph derivations….Pages 11-29
The monadic second-order logic of graphs : Definable sets of finite graphs….Pages 30-53
On systems of equations defining infinite graphs….Pages 54-73
Fault tolerant networks of specified diameter….Pages 74-86
DFS tree construction: Algorithms and characterizations….Pages 87-106
Serializable graphs….Pages 107-121
Transitive closure algorithms for very large databases….Pages 122-147
A graph-based decomposition approach for recursive query processing….Pages 148-165
Construction of deterministic transition graphs from dynamic integrity constraints….Pages 166-179
(Time × space)-efficient implementations of hlerarchical conceptual models….Pages 180-189
Dominance in the presence of obstacles….Pages 190-201
Separating a polyhedron by one translation from a set of obstacles….Pages 202-212
Linear time algorithms for testing approximate congruence in the plane….Pages 213-228
Moving regular k -gons in contact….Pages 229-242
Epsilon-nets for halfplanes….Pages 243-252
Greedy triangulation can be efficiently implemented in the average case….Pages 253-261
A simple systolic method to find all bridges of an undirected graph….Pages 262-267
Colouring perfect planar graphs in parallel….Pages 268-275
An efficient parallel algorithm for the all pairs shortest path problem….Pages 276-287
A parallel algorithm for channel routing….Pages 288-303
Application of graph theory to topology generation for logic gates….Pages 304-316
On the estimate of the size of a directed graph….Pages 317-326
The average size of ordered binary subgraphs….Pages 327-351
O(n 2 ) algorithms for graph planarization….Pages 352-377
Bandwidth and profile minimization….Pages 378-393
On the spanning trees of weighted graphs….Pages 394-405
On paths in search or decision trees which require almost worst-case time….Pages 406-423
A time-optimal parallel algorithm for the computing of Voronoi-diagrams….Pages 424-433
Voronoi diagrams in the moscow metric….Pages 434-441
A sweep algorithm and its implementation: The all-nearest-neighbors problem revisited….Pages 442-457