17. WG 1991: Fischbachau, Germany

Gunther Schmidt, Rudolf Berghammer (Eds.): 17th International Workshop, WG '91, Fischbachau, Germany, June 17-19, 1991, Proceedings. Lecture Notes in Computer Science 570 Springer 1992, ISBN 3-540-55121-2 BibTeX

Tree-Related Problems

Hans L. Bodlaender, John R. Gilbert, Ton Kloks, Hjálmtyr Hafsteinsson: Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height. 1-12 BibTeX
Bruno Courcelle, Mohamed Mosbah: Monadic Second-Order Evaluations on Tree-Decomposable Graphs. 13-24 BibTeX
Ralf Heckmann, Ralf Klasing, Burkhard Monien, Walter Unger: Optimal Embedding of Complete Binary Trees into Lines and Grids. 25-35 BibTeX

Yasuyoshi Okada, Masahiro Hayashi: Graph Rewriting Systems and their Application to Network Reliability Analysis. 36-47 BibTeX
Albert Zündorf, Andy Schürr: Nondeterministic Control Structures for Graph Rewriting Systems. 48-62 BibTeX
Marc Andries, Jan Paredaens: A Language for Generic Graph-Transformations. 63-74 BibTeX
Rudolf Freund, Brigitte Haberstroh: Attributed Elementarz Programmed Graph Grammars. 75-84 BibTeX

Edmund Ihler: The Complexity of Approximating the Class Steiner Tree Problem. 85-96 BibTeX
Zbigniew Lonc: On Complexity of Some Chain and Antichain Partition Problems. 97-104 BibTeX

Jurek Czyzowicz, Eduardo Rivera-Campo, Nicola Santoro, Jorge Urrutia, Joseph Zaks: Tight Bounds for the Rectangualr Art Gallery Problem. 105-112 BibTeX
Leonidas J. Guibas, Joseph S. B. Mitchell: Voronoi Diagrams of Moving Points in the Plane. 113-125 BibTeX

Takayoshi Shoudai: Using Maximal Independent Sets to Solve Problems in Parallel. 126-134 BibTeX
Zvi M. Kedem, Krishna V. Palem, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis: Fast Parallel Algorithms for Coloring Random Graphs. 135-147 BibTeX

Xiaoyi Jiang, Horst Bunke: Optimal Vertex Ordering of a Graph and its Application to Symmetry Detection. 148-158 BibTeX
Ondrej Sýkora, Imrich Vrto: Edge Separators for Graphs of Bounded Genus with Applications. 159-168 BibTeX
Ding-Zhu Du, Yuh-Dauh Lyuu, D. Frank Hsu: Line Digraph Iterations and Spread Concept - with Application to Graph Theory, Fault Tolerance, and Routing. 169-179 BibTeX
Ludek Kucera: A Generalized Encryption Scheme Based on Random Graphs. 180-186 BibTeX

Esteban Feuerstein, Alberto Marchetti-Spaccamela: Dynamic Algorithms for Shortest Paths in Planar Graphs. 187-197 BibTeX
Iain A. Stewart: Copmlete Problems for Logspace Involving Lexicographic First Paths in Graphs. 198-208 BibTeX
Tadao Takaoka: A New Upper Bound on the Complexity of the All Pairs Shortest Path Problem. 209-213 BibTeX

Ondrej Sýkora, Imrich Vrto: On the Crossing Number of the Hypercube and the Cube Connected Cycles. 214-218 BibTeX
Peter Damaschke: Logic Arrays for Interval Indicator Functions. 219-225 BibTeX
Elena Stöhr: On the Broadcast Time of the Butterfly network. 226-229 BibTeX

Hans L. Bodlaender: On Disjoint Cycles. 230-238 BibTeX
Andreas Brandstädt: Short Disjoint Cycles in Cubic Bridgeless Graphs. 239-249 BibTeX