Skip to main content
SpringerLink
Log in

Graph-Theoretic Concepts in Computer Science

18th International Workshop, WG '92, Wiesbaden-Naurod, Germany, June 18-20, 1992. Proceedings

  • Conference proceedings
  • © 1993

Overview

Editors:
  1. Ernst W. Mayr
    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 657)

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. On improved time bounds for permutation graph problems

    • Andreas Brandstädt
    Pages 1-10

  3. A simple test for interval graphs

    • Wen-Lian Hsu
    Pages 11-16

  4. Tolerance graphs and orders

    • Stefan Felsner
    Pages 17-26

  5. On scheduling problems restricted to interval orders

    • Klaus Jansen
    Pages 27-36

  6. Scheduling with incompatible jobs

    • Hans L. Bodlaender, Klaus Jansen, Gerhard J. Woeginger
    Pages 37-49

  7. Generalized coloring for tree-like graphs

    • Klaus Jansen, Petra Scheffler
    Pages 50-59

  8. Optimal (parallel) algorithms for the all-to-all vertices distance problem for certain graph classes

    • Elias Dahlhaus
    Pages 60-69

  9. Topology of parallel networks and computational complexity (extended abstract)

    • Juraj Hromkovič
    Pages 70-77

  10. Parallel triangulation of nonconvex polytopes

    • W. Preilowski
    Pages 78-89

  11. Kayles on special classes of graphs — An application of Sprague-Grundy theory

    • Hans L. Bodlaender
    Pages 90-102

  12. A linear time algorithm for isomorphism of graphs of bounded average genus

    • Jianer Chen
    Pages 103-113

  13. Improved algorithms for routing on two-dimensional grids

    • Dinesh Bhatia, Tom Leighton, Fillia Makedon, Carolyn H. Norton
    Pages 114-122

  14. Minimum rectilinear steiner trees for intervals on two parallel lines

    • Edmund Ihler
    Pages 123-134

  15. A new characterization of tree medians with applications to distributed algorithms

    • O. Gerstel, S. Zaks
    Pages 135-144

  16. The 3-edge-components and a structural description of all 3-edge-cuts in a graph

    • Efim Dinitz
    Pages 145-157

  17. On assembly of four-connected graphs

    • Jianer Chen, Arkady Kanevsky
    Pages 158-169

  18. On the homogeneous decomposition of graphs

    • Beverly Jamison, Stephan Olariu
    Pages 170-183

  19. Embeddings in recursive combinatorial networks

    • Sajal K. Das, Aisheng Mao
    Pages 184-204

  20. On shortcutting digraphs

    • Mikkel Thorup
    Pages 205-211
Back to top

Keywords

About this book

The 18th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '92) was held in Wiesbaden-Naurod, Germany, June 18-20, 1992. Itwas organized by the Department of Computer Science, Johann Wolfgang Goethe University, Frankfurt am Main. Contributions with original results inthe study and application of graph-theoretic concepts in various fields of computer science were solicited, and 72 papers were submitted and reviewed, from which 29 were selected for presentation at the workshop. The workshop was attended by 61 scientists from 16 countries. All 29 papers in the volume have undergone careful revision after the meeting, based on the discussions and comments from the audience and the referees. The volume is divided into parts on restricted graph classes, scheduling and related problems, parallel anbd distributed algorithms, combinatorial graph problems, graph decomposition, graph grammars and geometry, and modelling by graphs.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation