Skip to main content
SpringerLink
Log in
Book cover

Graph-Theoretic Concepts in Computer Science

17th International Workshop WG '91, Fischbachau, Germany, June 17-19, 1991. Proceedings

  • Conference proceedings
  • © 1992

Overview

Editors:
  1. Gunther Schmidt
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Rudolf Berghammer
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 570)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (25 papers)

  1. Front Matter

    Download chapter PDF

  2. Approximating treewidth, pathwidth, and minimum elimination tree height

    • Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson, Ton Kloks
    Pages 1-12

  3. Monadic second-order evaluations on tree-decomposable graphs

    • B. Courcelle, M. Mosbah
    Pages 13-24

  4. Optimal embedding of complete binary trees into lines and grids

    • R. Heckmann, R. Klasing, B. Monien, W. Unger
    Pages 25-35

  5. Graph rewriting systems and their application to network reliability analysis

    • Yasuyoshi Okada, Masahiro Hayashi
    Pages 36-47

  6. Nondeterministic control structures for graph rewriting systems

    • Albert Zündorf, Andy Schürr
    Pages 48-62

  7. A language for generic graph-transformations

    • Marc Andries, Jan Paredaens
    Pages 63-74

  8. Attributed elementary programmed graph grammars

    • Rudolf Freund, Brigitte Haberstroh
    Pages 75-84

  9. The complexity of approximating the class Steiner tree problem

    • Edmund Ihler
    Pages 85-96

  10. On complexity of some chain and antichain partition problems

    • Zbigniew Lonc
    Pages 97-104

  11. Tight bounds for the rectangular art gallery problem

    • J. Czyzowicz, E. Rivera-Campo, N. Santoro, J. Urrutia, J. Zaks
    Pages 105-112

  12. Voronoi diagrams of moving points in the plane

    • Leonidas J. Guibas, Joseph S. B. Mitchell, Thomas Roos
    Pages 113-125

  13. Using maximal independent sets to solve problems in parallel

    • Takayoshi Shoudai, Satoru Miyano
    Pages 126-134

  14. Fast parallel algorithms for coloring random graphs

    • Zvi M. Kedem, Krishna V. Palem, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis
    Pages 135-147

  15. Optimal vertex ordering of a graph and its application to symmetry detection

    • X. Y. Jiang, H. Bunke
    Pages 148-158

  16. Edge separators for graphs of bounded genus with applications

    • Ondrej Sýkora, Imrich Vrto
    Pages 159-168

  17. Line digraph iterations and the spread concept—with application to graph theory, fault tolerance, and routing

    • Ding-Zhu Du, Yuh-Dauh Lyuu, D. Frank Hsu
    Pages 169-179

  18. A generalized encryption scheme based on random graphs

    • Luděk Kučera
    Pages 180-186

  19. Dynamic algorithms for shortest paths in planar graphs

    • Esteban Feuerstein, Alberto Marchetti-Spaccamela
    Pages 187-197

  20. Complete problems for logspace involving lexicographic first paths in graphs

    • Iain A. Stewart
    Pages 198-208
Back to top

Keywords

About this book

This volume contains contributions to the 17th International workshop on Graph-Theoretic Concepts in Computer Science (WG '91) held in Southern Bavaria in June 1991. These annual workshops are designed to bring together researchers using graph-theoretic methods to discuss new developments relating to or emerging from a diversity of application fields. The topics covered in this volume include: tree-related problems, graph grammarsand rewriting, complexity, computational geometry, parallel algorithms, vertex orderings, path-oriented algorithms, applications to VLSI, and disjoint cycle problems.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation