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

by Jan Van Leeuwen (editor)

NC-algorithms for graphs with small treewidth.- Graph-theoretic properties compatible with graph derivations.- The monadic second-order logic of graphs : Definable sets of finite graphs.- On systems of equations defining infinite graphs.- Fault tolerant networks of specified diameter.- DFS tree Algorithms and characterizations.- Serializable graphs.- Transitive closure algorithms for very large databases.- A graph-based decomposition approach for recursive query processing.- Construction of deterministic transition graphs from dynamic integrity constraints.- (Time × space)-efficient implementations of hlerarchical conceptual models.- Dominance in the presence of obstacles.- Separating a polyhedron by one translation from a set of obstacles.- Linear time algorithms for testing approximate congruence in the plane.- Moving regular k-gons in contact.- Epsilon-nets for halfplanes.- Greedy triangulation can be efficiently implemented in the average case.- A simple systolic method to find all bridges of an undirected graph.- Colouring perfect planar graphs in parallel.- An efficient parallel algorithm for the all pairs shortest path problem.- A parallel algorithm for channel routing.- Application of graph theory to topology generation for logic gates.- On the estimate of the size of a directed graph.- The average size of ordered binary subgraphs.- O(n2) algorithms for graph planarization.- Bandwidth and profile minimization.- On the spanning trees of weighted graphs.- On paths in search or decision trees which require almost worst-case time.- A time-optimal parallel algorithm for the computing of Voronoi-diagrams.- Voronoi diagrams in the moscow metric.- A sweep algorithm and its The all-nearest-neighbors problem revisited.

472 pages, Paperback

First published February 21, 1989