Skip to main content
SpringerLink
Log in

Graph-Theoretic Concepts in Computer Science

22nd International Workshop, WG '96, Cadenabbia, Italy, June 12-14, 1996, Proceedings

  • Conference proceedings
  • © 1997

Overview

Editors:
  1. Fabrizio d'Amore
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Paolo Giulio Franciosa
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Alberto Marchetti-Spaccamela
    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 1197)

Included in the following conference series:

Conference proceedings info: WG 1996.

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 (31 papers)

  1. Front Matter

    Download chapter PDF

  2. Hypergraphs and decision trees

    • Andrew C. Yao
    Pages 1-1

  3. Improved approximations of independent dominating set in bounded degree graphs

    • Paola Alimonti, Tiziana Calamoneri
    Pages 2-16

  4. A new characterization of P 4-connected graphs

    • Luitpold Babel, Stephan Olariu
    Pages 17-30

  5. Node rewriting in hypergraphs

    • Michel Bauderon, Hélène Jacquet
    Pages 31-43

  6. On κ-partitioning the n-cube

    • Sergej L. Bezrukov
    Pages 44-55

  7. Embedding complete binary trees in product graphs

    • Adrienne Broadwater, Kemal Efe, Antonio Fernández
    Pages 56-66

  8. Clique and anticlique partitions of graphs

    • Krzysztof BryÅ›, Zbigniew Lonc
    Pages 67-72

  9. Optimal parallel routing in star graphs

    • Chi-Chang Chen, Jianer Chen
    Pages 73-84

  10. Counting edges in a dag

    • Serafino Cicerone, Daniele Frigioni, Umberto Nanni, Francesco Pugliese
    Pages 85-100

  11. Closure properties of context-free Hyperedge Replacement Systems

    • Ornella Ciotti, Francesco Parisi-Presicce
    Pages 101-113

  12. Upward drawings of search trees

    • P. Crescenzi, P. Penna
    Pages 114-125

  13. More general parallel tree contraction: Register allocation and broadcasting in a tree

    • Krzysztof Diks, Torben Hagerup
    Pages 126-140

  14. System diagnosis with smallest risk of error

    • Krzysztof Diks, Andrzej Pelc
    Pages 141-150

  15. Efficient algorithms for shortest path queries in planar digraphs

    • Hristo N. Djidjev
    Pages 151-165

  16. LexBFS-orderings and powers of graphs

    • Feodor F. Dragan, Falk Nicolai, Andreas Brandstädt
    Pages 166-180

  17. Efficient Union-Find for planar graphs and other sparse graph classes

    • Jens Gustedt
    Pages 181-195

  18. Switchbox routing in VLSI design: Closing the complexity gap

    • Stephan Hartmann, Markus W. Schäffter, Andreas S. Schulz
    Pages 196-210

  19. Detecting diamond necklaces in labeled dags

    • Michel Hurfin, Michel Raynal
    Pages 211-223

  20. Algebraic graph derivations for graphical calculi

    • Wolfram Kahl
    Pages 224-238
Back to top

Other volumes

  1. Graph-Theoretic Concepts in Computer Science

Keywords

About this book

This book constitutes the carefully refereed post-proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG '96, held in Cadenabbia, Italy, in June 1996.
The 30 revised full papers presented in the volume were selected from a total of 65 submissions. This collection documents the state of the art in the area. Among the topics addressed are graph algorithms, graph rewriting, hypergraphs, graph drawing, networking, approximation and optimization, trees, graph computation, and others.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation