Graph-Theoretic Concepts in Computer Science: 15th International Workshop WG ’89 Castle Rolduc, The Netherlands, June 14–16, 1989 Proceedings

Seshu Madhavapeddy, I. Hal Sudborough (auth.), Manfred Nagl (eds.)3540522921, 9783540522928

The aim of this workshop series is to contribute to integration in computer science by applying graph-theoretic concepts. Commonalities between various fields of specialization in computer science may be detected by applying graph-theoretic concepts. The workshops are unusual in that they combine theoretical aspects with practice and applications. Applications dealt with in this volume include the use of graph-theoretic concepts in distributed and parallel computation, VLSI, CAD, software engineering, computer graphics, data structures, and computational geometry.

---

Table of contents :
Disjoint paths in the hypercube….Pages 3-18
Time bounds for broadcasting in bounded degree graphs….Pages 19-33
t/s -Diagnosable systems: A characterization and diagnosis algorithm….Pages 34-45
Toward a complete representation of graphoids in graphs — Abridged Version….Pages 46-62
CADULA — A graph-based model for monitoring CAD-processes….Pages 63-77
On hyperedge replacement and BNLC graph grammars….Pages 78-93
Graph rewriting systems with priorities….Pages 94-106
Filtering hyperedge-replacement languages through compatible properties….Pages 107-120
Describing distributed systems by categorical graph grammars….Pages 121-135
A parser for context free plex grammars….Pages 136-150
Introduction to PROGRESS, an attribute graph grammar based specification language….Pages 151-165
On the complexity of optimal drawings of graphs….Pages 166-180
Bounds to the page number of partially ordered sets….Pages 181-195
Beyond Steiner’s problem: A VLSI oriented generalization….Pages 196-210
A fast sequential and parallel algorithm for the computation of the k-closure of a graph….Pages 211-217
On feedback problems in digraphs….Pages 218-231
Improved self-reduction algorithms for graphs with bounded treewidth….Pages 232-244
Finding a minimal transitive reduction in a strongly connected digraph within linear time….Pages 245-259
Paging binary trees with external balancing….Pages 260-276
The complexity of graph problems for succinctly represented graphs….Pages 277-286
An O ( n log n ) algorithm for 1-D tile compaction….Pages 287-301
Weighted parallel triangulation of simple polygons….Pages 302-315
Implementing data structures on a hypercube multiprocessor, and applications in parallel computational geometry….Pages 316-329
k — Nearest — Neighbor Voronoi diagrams for sets of convex polygons, line segments and points….Pages 330-340
Finding squares and rectangles in sets of points….Pages 341-355
Combinatorial properties of abstract Voronoi diagrams….Pages 356-369