Skip to main content
SpringerLink
Log in

Graph-Theoretic Concepts in Computer Science

16th International Workshop WG '90, Berlin, Germany, June 20-22, 1990

  • Conference proceedings
  • © 1991

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 484)

Included in the following conference series:

Conference proceedings info: WG 1990.

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

  1. Front Matter

    Download chapter PDF

  2. Optimal parallel algorithms for sparse graphs

    • Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis
    Pages 1-17

  3. Finding minimally weighted subgraphs

    • Jürgen Plehn, Bernd Voigt
    Pages 18-29

  4. On the complexity of some coloring games

    • Hans L. Bodlaender
    Pages 30-40

  5. A generalized best-first search method in graphs

    • Ulrich Huckenbeck, Detlev Ruland
    Pages 41-60

  6. Avoiding matrix multiplication

    • Tze-Heng Ma, Jeremy P. Spinrad
    Pages 61-71

  7. Induced subraph isomorphism for cographs is NP-complete

    • Peter Damaschke
    Pages 72-78

  8. On feedback problems in planar digraphs

    • Hermann Stamm
    Pages 79-89

  9. Recognizing binary hamming graphs in O(n 2 log n) time

    • Franz Aurenhammer, Johann Hagauer
    Pages 90-98

  10. Vertex-disjoint trees and boundary single-layer routing

    • Kuo-Feng Liao, Majid Sarrafzadeh
    Pages 99-108

  11. Bounds on the quality of approximate solutions to the group Steiner problem

    • Edmund Ihler
    Pages 109-118

  12. Two polynomial problems in PLA folding

    • Claudio Arbib
    Pages 119-129

  13. The VLSI layout problem in various embedding models

    • Michael Formann, Frank Wagner
    Pages 130-139

  14. Approximating the minimum net expansion: Near optimal solutions to circuit partitioning problems

    • Fillia Makedon, Spyros Tragoudas
    Pages 140-153

  15. Deterministic message routing in faulty hypercubes

    • Seshu Madhavapeddy, I. Hal Sudborough
    Pages 154-169

  16. On complexity of a message-routing strategy for multicomputer systems

    • Hyeong-Ah Choi, Abdol-Hossein Esfahanian
    Pages 170-181

  17. Embeddings of treelike graphs into 2-dimensional meshes

    • Peter Zienicke
    Pages 182-192

  18. Diagnosis of t/s-diagnosable systems

    • A. Das, K. Thulasiraman
    Pages 193-205

  19. Deciding 1-solvability of distributed task is NP-hard

    • Ofer Biran, Shlomo Moran, Shmuel Zaks
    Pages 206-220

  20. Remarks on some concurrency measures

    • M. Habib, M. Morvan, J. X. Rampon
    Pages 221-238
Back to top

Other volumes

  1. Graph-Theoretic Concepts in Computer Science

Keywords

About this book

This volume gives the proceedings of WG '90, the 16th in a series of workshops. The aim of the workshop series is to contribute to integration in computer science by applying graph-theoretic concepts. The workshops are unusual in that they combine theoretical aspects with practice and applications. The volume is organized into sections on: - Graph algorithms and complexity, - VLSI layout, - Multiprocessor systems and concurrency, - Computational geometry, - Graphs, languages and databases, - Graph grammars. The volume contains revised versions of nearly all the papers presented at the workshop. Several papers take the form of preliminary reports on ongoing research.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation