Skip to main content
SpringerLink
Log in

Graph-Theoretic Concepts in Computer Science

26th International Workshop, WG 2000 Konstanz, Germany, June 15-17, 2000 Proceedings

  • Conference proceedings
  • © 2000

Overview

Editors:
  1. Ulrik Brandes

    1. Department of Computer and Information Science, University of Konstanz, Konstanz, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Dorothea Wagner

    1. Department of Computer and Information Science, University of Konstanz, Konstanz, Germany

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

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
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 (28 papers)

  1. Front Matter

    Pages I-X
    Download chapter PDF

  2. On the Expected Runtime and the Success Probability of Evolutionary Algorithms (Invited Presentation)

    • Ingo Wegener
    Pages 1-10

  3. n Points and One Line: Analysis of Randomized Games (Abstract of Invited Lecture)

    • Emo Welzl
    Pages 11-12

  4. Approximating Call-Scheduling Makespan in All-Optical Networks

    • Luca Becchetti, Miriam Di Ianni, Alberto Marchetti-Spaccamela
    Pages 13-22

  5. New Spectral Lower Bounds on the Bisection Width of Graphs

    • Sergei L. Bezrukov, Robert Elsässer, Burkhard Monien, Robert Preis, Jean-Pierre Tillich
    Pages 23-34

  6. Traversing Directed Eulerian Mazes (Extended Abstract)

    • Sandeep Bhatt, Shimon Even, David Greenberg, Rafi Tayar
    Pages 35-46

  7. On the Space and Access Complexity of Computation DAGs

    • Gianfranco Bilardi, Andrea Pietracaprina, Paolo D’Alberto
    Pages 47-58

  8. Approximating the Treewidth of AT-Free Graphs

    • Vincent Bouchitté, Ioan Todinca
    Pages 59-70

  9. Split-Perfect Graphs: Characterizations and Algorithmic Use

    • Andreas Brandstädt, Van Bang Le
    Pages 71-82

  10. Coarse Grained Parallel Algorithms for Detecting Convex Bipartite Graphs

    • Edson Cáceres, Albert Chan, Frank Dehne, Giuseppe Prencipe
    Pages 83-94

  11. Networks with Small Stretch Number (Extended Abstract)

    • Serafino Cicerone, Gabriele Di Stefano
    Pages 95-106

  12. Efficient Dispersion Algorithms for Geometric Intersection Graphs

    • Peter Damaschke
    Pages 107-115

  13. Optimizing Cost Flows by Modifying Arc Costs and Capacities

    • Ingo Demgensky, Hartmut Noltemeier, Hans-Christoph Wirth
    Pages 116-126

  14. Update Networks and Their Routing Strategies

    • Michael J. Dinneen, Bakhadyr Khoussainov
    Pages 127-136

  15. Computing Input Multiplicity in Anonymous Synchronous Networks with Dynamic Faults

    • Stefan Dobrev
    Pages 137-148

  16. Diameter of the Knödel Graph

    • Guillaume Fertin, André Raspaud, Heiko Schröder, Ondrej Sýkora, Imrich VrÅ¥o
    Pages 149-160

  17. On the Domination Search Number

    • Fedor Fomin, Dieter Kratsch, Haiko Müller
    Pages 161-171

  18. Efficient Communication in Unknown Networks

    • Luisa Gargano, Andrzej Pelc, Stephane Perennes, Ugo Vaccaro
    Pages 172-183

  19. Graph Coloring on a Coarse Grained Multiprocessor (Extended Abstract)

    • Assefaw Hadish Gebremedhin, Isabelle Guérin Lassous, Jens Gustedt, Jan Arne Telle
    Pages 184-195

  20. The Tree-Width of Clique-Width Bounded Graphs without Kn,n

    • Frank Gurski, Egon Wanke
    Pages 196-205
Back to top

Keywords

About this book

The 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000) was held at Waldhaus Jakob, in Konstanz, Germany, on 15{ 17 June 2000. It was organized by the Algorithms and Data Structures Group of the Department of Computer and Information Science, University of K- stanz, and sponsored by Deutsche Forschungsgemeinschaft (DFG) and Univ- sit¨atsgesellschaft Konstanz. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer science, or by extracting new problems from applications. The goal is to present recent research results and to identify and explore directions for future research. The workshop looks back on a remarkable tradition of more than a quarter of a century. Previous Workshops have been organized in various places in Europe, and submissions come from all over the world. This year, 57 attendees from 13 di erent countries gathered in the relaxing atmosphere of Lake Constance, also known as the Bodensee. Out of 51 submis- ons, the program committee carefully selected 26 papers for presentation at the workshop. This selection re?ects current research directions, among them graph and network algorithms and their complexity, algorithms for special graph cl- ses, communication networks, and distributed algorithms. The present volume contains these papers together with the survey presented in an invited lecture by Ingo Wegener (University of Dortmund) and an extended abstract of the invited lecture given by Emo Welzl (ETH Zuric ¨ h).

Editors and Affiliations

  • Department of Computer and Information Science, University of Konstanz, Konstanz, Germany

    Ulrik Brandes, Dorothea Wagner

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation