14. WG 1988: Amsterdam, The Netherlands

Jan van Leeuwen (Ed.): Graph-Theoretic Concepts in Computer Science, 14th International Workshop, WG '88, Amsterdam, The Netherlands, June 15-17, 1988, Proceedings. Lecture Notes in Computer Science 344 Springer 1989, ISBN 3-540-50728-0

Session 1

Hans L. Bodlaender:
NC-Algorithms for Graphs with Small Treewidth. 1-10
Annegret Habel:
Graph-Theoretic Properties Compatible with Graph Derivations. 11-29
Bruno Courcelle:
The Monadic Second-Order Logic of Graphs: Definable Sets of Finite Graphs. 30-53
Michel Bauderon:
On Systems of Equations Defining Infinite Graphs. 54-73
Henk Meijer, R. Dawes:
Fault Tolerant Networks of Specified Diameter. 74-86
Ephraim Korach, Zvi Ostfeld:
DFS Tree Construction: Algorithms and Characterizations. 87-106

Session 2

K. Vidyasankar:
Serializable Graphs. 107-121
Joachim Biskup, Holger Stiefeling:
Transitive Closure Algorithms for Very Large Databases. 122-147
Dietmar Seipel:
A Graph-Based Decomposition Approach for Recursive Query Processing. 148-165
Udo W. Lipeck, Dasu Feng:
Construction of Deterministic Transition Graphs from Dynamic Integrity Constraints. 166-179
Nicola Santoro:
(Time × Space)-Efficient Implementations of Hierarchical Conceptual Models. 180-189

Session 3

Mark de Berg, Mark H. Overmars:
Dominance in the Presence of Obstracles. 190-201
Otto Nurmi, Jörg-Rüdiger Sack:
Separating a Polyhedron by One Translation from a Set of Obstacles (Extended Abstract). 202-212
Sebastian Iwanowski:
Linear Time Algorithms for Testing Approximate Congruence in the Plane. 213-228
Stephan Abramowski, Bruno Lang, Heinrich Müller:
Moving Regular k-Gons in Contact. 229-242
Gerhard J. Woeginger:
Epsilon-Nets for Halfplanes. 243-252
Andrzej Lingas:
Greedy Triangulation acn be Efficiently Implemented in the Average Case (Extended Abstract). 253-261

Session 4

Manfred Schimmler, Heiko Schröder:
A Simple Systolic Method to Find all Bridges of an Undirected Graph. 262-267
Iain A. Stewart:
Colouring Perfect Planar Graphs in Parallel. 268-275
Tadao Takaoka:
An Efficient Parallel Algorithm for the All Pairs Shortest Path Problem. 276-287
John E. Savage, Markus G. Wloka:
A Parallel Algorithm for Channel Routing. 288-303
Hubert Kaeslin:
Application of Graph Theory to Topology Generation for Logic Gates. 304-316

Session 5

Alberto Marchetti-Spaccamela:
On the Estimate of a Directed Graph. 317-326
Pieter H. Hartel:
The Average Size of Ordered Binary Subgraphs. 327-351
R. Jayakumar, Krishnaiyan Thulasiraman, M. N. S. Swamy:
O(n²) Algorithms for Graph Planarization. 352-377
Manfred Wiegers, Burkhard Monien:
Bandwidth and Profile Minimization. 378-393
Ernst W. Mayr, C. Greg Plaxton:
On the Spanning Trees of Weighted Graphs. 394-405
Ulrich Huckenbeck:
On Paths in Search or Decision Trees Which Require Almost Worst-Case Time. 406-423

Session 6

W. Preilowski, W. Mumbeck:
A Time-Optimal Parallel Algorithm for the Computing of Voronoi-Diagrams. 424-433
Rolf Klein:
Voronoi Diagrams in the Moscow Metric (Extended Abstract). 434-441
Klaus Hinrichs, Jürg Nievergelt, Peter Schorn:
A Sweep Algorithm and its Implementation: The All-Nearest-Neighbors Problem Revisited. 442-457