Skip to main content
SpringerLink
Log in
Book cover

Graph-Theoretic Concepts in Computer Science

23rd International Workshop, WG'97, Berlin, Germany, June 18-20, 1997. Proceedings

  • Conference proceedings
  • © 1997

Overview

Editors:
  1. Rolf H. Möhring
    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 1335)

Included in the following conference series:

Conference proceedings info: WG 1997.

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

  1. Front Matter

    Download chapter PDF

  2. Gadgets, approximation, and linear programming: Improved hardness results for cut and satisfiability problems

    • David P. Williamson
    Pages 1-1

  3. Non-oblivious local search for MAX 2-CCSP with application to MAX DICUT

    • Paola Alimonti
    Pages 2-14

  4. On the number of simple cycles in planar graphs

    • Helmut Alt, Ulrich Fuchs, Klaus Kriegel
    Pages 15-24

  5. On the separable-homogeneous decomposition of graphs

    • Luitpold Babel, Stephan Olariu
    Pages 25-37

  6. Pseudo-hamiltonian graphs

    • Luitpold Babel, Gerhard J. Woeginger
    Pages 38-51

  7. Acyclic orientations for deadlock prevention in interconnection networks

    • Jean-Claude Bermond, Miriam Di Ianni, Michele Flammini, Stephane Perennes
    Pages 52-64

  8. Weak-order extensions of an order

    • Karell Bertet, Jens Gustedt, Michel Morvan
    Pages 65-77

  9. An upper bound for the maximum cut mean value

    • Alberto Bertoni, Paola Campadelli, Roberto Posenato
    Pages 78-84

  10. NP-completeness results for minimum planar spanners

    • Ulrik Brandes, Dagmar Handke
    Pages 85-99

  11. Computing the independence number of dense triangle-free graphs

    • Stephan Brandt
    Pages 100-108

  12. Algorithms for the treewidth and minimum fill-in of HHD-free graphs

    • H. J. Broersma, E. Dahlhaus, T. Kloks
    Pages 109-117

  13. Block decomposition of inheritance hierarchies

    • Christian Capelle
    Pages 118-131

  14. Minimal elimination ordering inside a given chordal graph

    • Dias Dahlhaus
    Pages 132-143

  15. On-line algorithms for networks of temporal constraints

    • Fabrizio d'Amore, Fabio Iacobini
    Pages 144-156

  16. Parallel algorithms for treewidth two

    • Babette de Fluiter, Hans L. Bodlaender
    Pages 157-170

  17. On optimal graphs embedded into paths and rings, with analysis using l 1-spheres

    • Yefim Dinitz, Marcelo Feighelstein, Shmuel Zaks
    Pages 171-183

  18. On greedy matching ordering and greedy matchable graphs

    • Feodor F. Dragan
    Pages 184-198

  19. Off-line and on-line call-scheduling in stars and trees

    • Thomas Erlebach, Klaus Jansen
    Pages 199-213

  20. Computational complexity of the Krausz dimension of graphs

    • Petr Hliněný, Jan Kratochvíl
    Pages 214-228
Back to top

Other volumes

  1. Graph-Theoretic Concepts in Computer Science

Keywords

About this book

This book constitutes the strictly refereed post-workshop proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG'97, held in Berlin, Germany in June 1997.
The volume presents 28 revised full papers carefully selected for inclusion in the book from 42 submissions. The papers address a variety of graph-theoretic issues relevant from the computer science point of view such as graph algorithms, cycles, graph decompositions, interconnection networks, local search, graph orderings, graph matching, graph languages, tree-width computation, etc.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation