Graph-Theoretic Concepts in Computer Science: 15th International Workshop WG '89, Castle Rolduc, The Netherlands, June 14-16, 1989, Proceedings (Lecture Notes in Computer Science, 411)

"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."--MU TOC PP 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 In this paper we study the problem of finding disjoint paths in a hypercube.