16. WG 1990: Berlin, Germany

Rolf H. Möhring (Ed.): Graph-Theoretic Concepts in Computer Science, 16rd International Workshop, WG '90, Berlin, Germany, June 20-22, 1990, Proceedings. Lecture Notes in Computer Science 484 Springer 1991, ISBN 3-540-53832-1 BibTeX

Graph Algorithms and Complexity

Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis: Optimal Parallel Algorithms for Sparse Graphs. 1-17 BibTeX
Jürgen Plehn, Bernd Voigt: Finding Minimally Weighted Subgraphs. 18-29 BibTeX
Hans L. Bodlaender: On the Complexity of Some Coloring Games. 30-40 BibTeX
Ulrich Huckenbeck, Detlev Ruland: A Generalized Best-First Search Method in Graphs. 41-60 BibTeX
Tze-Heng Ma, Jeremy Spinrad: Avoiding Matrix Multiplication. 61-71 BibTeX
Peter Damaschke: Induced Subgraph Isomorphism for Cographs in NP-Complete. 72-78 BibTeX
Hermann Stamm: On Feedback Problems in Planar Digraphs. 79-89 BibTeX
Franz Aurenhammer, Johann Hagauer: Recognizing Binary Hamming Graphs in O(n² log n) Time. 90-98 BibTeX

VLSI Layout

Kuo-Feng Liao, Majid Sarrafzadeh: Vertex-Disjoint Trees and Boundary Single-Layer Routing. 99-108 BibTeX
Edmund Ihler: Bounds on the quality of approximate solutions to the Group Steiner Problem. 109-118 BibTeX
Claudio Arbib: Two Polynomial Problems in PLA Folding. 119-129 BibTeX
Michael Formann, Frank Wagner: The VLSI layout in various embedding models. 130-139 BibTeX
Fillia Makedon, Spyros Tragoudas: Approximating the minimum net expansion: Near optimal solutions to circuit partitioning problems. 140-153 BibTeX

Multiprocessor Systems and Concurrency

Seshu Madhavapeddy, Ivan Hal Sudborough: Deterministic Message Routing in Faulty Hypercubes. 154-169 BibTeX
Hyeong-Ah Choi, Abdol-Hossein Esfahanian: On Complexity of a Message-Routing Strategy for Multicomputer Systems. 170-181 BibTeX
Peter Zienicke: Embeddings of Treelike Graphs into 2-Dimensional Meshes. 182-192 BibTeX
Anindya Das, Krishnaiyan Thulasiraman: Diagnosis of t/s-Diagnosable Systems. 193-205 BibTeX
Ofer Biran, Shlomo Moran, Shmuel Zaks: Deciding 1-sovability of distributed task is NP-hard. 206-220 BibTeX
Michel Habib, Michel Morvan, Jean-Xavier Rampon: Remarks on Some Concurrency Measures. 221-238 BibTeX

Computational Geometry

Frank Hoffmann, Michael Kaufmann: On the Rectilinear Art Gallery Problem - Algorithmic Aspects. 239-250 BibTeX
Paul Fischer, Hans-Ulrich Simon: Separation Problems and Circular Arc Systems. 251-259 BibTeX
Klaus Reuter, Ivan Rival: Genus of Order and Lattices. 260-275 BibTeX

Graphs, Languages and Databases

Iain A. Stewart: Comparing the expressibility of two languages formed using NP-complete graph operators. 276-290 BibTeX
Dietmar Seipel: Decomposition of Linear Recursive Logic Programs. 291-310 BibTeX

Graph Grammars

Didier Caucal, Roland Monfort: On the transition graphs of automata and grammars. 311-337 BibTeX
Michael Löwe, Hartmut Ehrig: Algebraic Approach to Graph Transformation Based on Single Pushout Derivations. 338-353 BibTeX