Graph-Theoretic Concepts in Computer Science: 20th International Workshop. WG '94, Herrsching, Germany, June 16 - 18, 1994. Proceedings | SpringerLink
Skip to main content
Springer Nature Link
Log in

Graph-Theoretic Concepts in Computer Science

20th International Workshop. WG '94, Herrsching, Germany, June 16 - 18, 1994. Proceedings

  • Conference proceedings
  • © 1995

Overview

Editors:
  1. Ernst W. Mayr
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Gunther Schmidt
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Gottfried Tinhofer
    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 903)

Included in the following conference series:

Conference proceedings info: WG 1994.

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 JPY 7149
Price includes VAT (Japan)
  • 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

About this book

This volume presents the proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '94), held in Herrsching, Germany in June 1994.
The volume contains 32 thoroughly revised papers selected from 66 submissions and provides an up-to-date snapshot of the research performed in the field. The topics addressed are graph grammars, treewidth, special graph classes, algorithms on graphs, broadcasting and architecture, planar graphs and related problems, and special graph problems.

Similar content being viewed by others

Keywords

Table of contents (32 papers)

  1. Front Matter

    Download chapter PDF

  2. Domino treewidth

    • Hans L. Bodlaender, Joost Engelfriet
    Pages 1-13

  3. A lower bound for treewidth and its consequences

    • Siddharthan Ramachandramurthi
    Pages 14-25

  4. Tree-width and path-width of comparability graphs of interval orders

    • Renate Garbe
    Pages 26-37

  5. A declarative approach to graph based modeling

    • Jürgen Ebert, Angelika Franzke
    Pages 38-50

  6. Multilevel graph grammars

    • Francesco Parisi-Presicce, Gabriele Piersanti
    Pages 51-64

  7. The algorithmic use of hypertree structure and maximum neighbourhood orderings

    • Andreas Brandstädt, Victor D. Chepoi, Feodor F. Dragan
    Pages 65-80

  8. On domination elimination orderings and domination graphs

    • Elias Dahihaus, Peter Hammer, Frédéric Maffray, Stephan Olariu
    Pages 81-92

  9. Complexity of graph covering problems

    • Jan Kratochvíl, Andrzej Proskurowski, Jan Arne Telle
    Pages 93-105

  10. Dominoes

    • T. Kloks, D. Kratsch, H. Müller
    Pages 106-120

  11. GLB-closures in directed acyclic graphs and their applications

    • Volker Turau, Weimin Chen
    Pages 121-129

  12. Minimum vertex cover, distributed decision-making, and communication complexity

    • Pierluigi Crescenzi, Luca Trevisan
    Pages 130-139

  13. Cartesian products of graphs as spanning subgraphs of de Bruijn graphs

    • Thomas Andreae, Michael Nölle, Gerald Schreiber
    Pages 140-150

  14. Specification of graph translators with triple graph grammars

    • Andy Schürr
    Pages 151-163

  15. Using programmed graph rewriting for the formal specification of a configuration management system

    • Bernhard Westfechtel
    Pages 164-179

  16. Exponential time analysis of confluent and boundary eNCE graph languages

    • K. Skodinis, E. Wanke
    Pages 180-192

  17. Time-optimal tree computations on sparse meshes

    • D. Bhagavathi, V. Bokka, H. Gurla, S. Olariu, J. L. Schwing
    Pages 193-205

  18. Prefix graphs and their applications

    • Shiva Chaudhuri, Torben Hagerup
    Pages 206-218

  19. The complexity of broadcasting in planar and decomposable graphs

    • Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer
    Pages 219-231

  20. The maximal f-dependent set problem for planar graphs is in NC

    • Zhi -Zhong Chen
    Pages 232-241
Back to top

Other volumes

  1. Graph-Theoretic Concepts in Computer Science

Bibliographic Information

Publish with us

Policies and ethics

Back to top