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

Graph Algorithms and Complexity

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

VLSI Layout

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

Multiprocessor Systems and Concurrency

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

Computational Geometry

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

Graphs, Languages and Databases

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

Graph Grammars

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

Last update Wed Feb 15 05:21:48 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page