Graph-Theoretic Concepts in Computer Science: 16th International Workshop WG ’90 Berlin, Germany, June 20–22, 1990 Proceedings

Grammati E. Pantziou, Paul G. Spirakis (auth.), Rolf H. Möhring (eds.)3540538321, 9783540538325

This volume gives the proceedings of WG ’90, the 16th in a series of workshops. The aim of the workshop series is to contribute to integration in computer science by applying graph-theoretic concepts. The workshops are unusual in that they combine theoretical aspects with practice and applications. The volume is organized into sections on: – Graph algorithms and complexity, – VLSI layout, – Multiprocessor systems and concurrency, – Computational geometry, – Graphs, languages and databases, – Graph grammars. The volume contains revised versions of nearly all the papers presented at the workshop. Several papers take the form of preliminary reports on ongoing research.

---

Table of contents :
Optimal parallel algorithms for sparse graphs….Pages 1-17
Finding minimally weighted subgraphs….Pages 18-29
On the complexity of some coloring games….Pages 30-40
A generalized best-first search method in graphs….Pages 41-60
Avoiding matrix multiplication….Pages 61-71
Induced subraph isomorphism for cographs is NP-complete….Pages 72-78
On feedback problems in planar digraphs….Pages 79-89
Recognizing binary hamming graphs in O ( n 2 log n ) time….Pages 90-98
Vertex-disjoint trees and boundary single-layer routing….Pages 99-108
Bounds on the quality of approximate solutions to the group Steiner problem….Pages 109-118
Two polynomial problems in PLA folding….Pages 119-129
The VLSI layout problem in various embedding models….Pages 130-139
Approximating the minimum net expansion: Near optimal solutions to circuit partitioning problems….Pages 140-153
Deterministic message routing in faulty hypercubes….Pages 154-169
On complexity of a message-routing strategy for multicomputer systems….Pages 170-181
Embeddings of treelike graphs into 2-dimensional meshes….Pages 182-192
Diagnosis of t/s-diagnosable systems….Pages 193-205
Deciding 1-solvability of distributed task is NP-hard….Pages 206-220
Remarks on some concurrency measures….Pages 221-238
On the rectilinear art gallery problem algorithmic aspects….Pages 239-250
Separation problems and circular arc systems….Pages 251-259
Genus of orders and lattices….Pages 260-275
Comparing the expressibility of two languages formed using NP-complete graph operators….Pages 276-290
Decomposition of linear recursive logic programs….Pages 291-310
On the transition graphs of automata and grammars….Pages 311-337
Algebraic approach to graph transformation based on single pushout derivations….Pages 338-353