Skip to main content
SpringerLink
Log in

Graph-Theoretic Concepts in Computer Science

30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers

  • Conference proceedings
  • © 2005

Overview

Editors:
  1. Juraj Hromkovič

    1. Department of Computer Science, ETH Zurich, ETH Zentrum, Zurich, Switzerland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Manfred Nagl

    1. Department of Computer Science, RWTH Aachen, Chair of Computer Science III, Aachen, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Bernhard Westfechtel

    1. Department of Computer Science III, RWTH Aachen University, Aachen, 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 3353)

Included in the following conference series:

Conference proceedings info: WG 2004.

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

  1. Front Matter

    Download chapter PDF

  2. Invited Papers

    1. Lexicographic Breadth First Search – A Survey

      • Derek G. Corneil
      Pages 1-19

    2. Wireless Networking: Graph Theory Unplugged

      • Roger Wattenhofer
      Pages 20-32

  3. Graph Algorithms: Trees

    1. Constant Time Generation of Trees with Specified Diameter

      • Shin-ichi Nakano, Takeaki Uno
      Pages 33-45

    2. Treelike Comparability Graphs: Characterization, Recognition, and Applications

      • Sabine Cornelsen, Gabriele Di Stefano
      Pages 46-57

    3. Elegant Distance Constrained Labelings of Trees

      • Jiří Fiala, Petr A. Golovach, Jan Kratochvíl
      Pages 58-67

    4. Collective Tree Spanners and Routing in AT-free Related Graphs

      • Feodor F. Dragan, Chenyu Yan, Derek G. Corneil
      Pages 68-80

  4. Graph Algorithms: Recognition and Decomposition

    1. On the Maximum Cardinality Search Lower Bound for Treewidth

      • Hans L. Bodlaender, Arie M. C. A. Koster
      Pages 81-92

    2. Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs

      • Christophe Crespelle, Christophe Paul
      Pages 93-104

    3. Recognizing HHD-free and Welsh-Powell Opposition Graphs

      • Stavros D. Nikolopoulos, Leonidas Palios
      Pages 105-116

    4. Bimodular Decomposition of Bipartite Graphs

      • Jean-Luc Fouquet, Michel Habib, Fabien de Montgolfier, Jean-Marie Vanherpe
      Pages 117-128

    5. Coloring a Graph Using Split Decomposition

      • Michaël Rao
      Pages 129-141

  5. Graph Algorithms: Various Problems

    1. Decremental Clique Problem

      • Fabrizio Grandoni, Giuseppe F. Italiano
      Pages 142-153

    2. A Symbolic Approach to the All-Pairs Shortest-Paths Problem

      • Daniel Sawitzki
      Pages 154-167

    3. Minimal de Bruijn Sequence in a Language with Forbidden Substrings

      • Eduardo Moreno, Martín Matamala
      Pages 168-176

    4. A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic \(\mathcal{EL}\)

      • Franz Baader
      Pages 177-188

  6. Optimization and Approximation Algorithms

    1. The Computational Complexity of the Minimum Weight Processor Assignment Problem

      • Hajo J. Broersma, Daniel Paulusma, Gerard J. M. Smit, Frank Vlaardingerbroek, Gerhard J. Woeginger
      Pages 189-200

    2. A Stochastic Location Problem with Applications to Tele-diagnostic

      • Nicola Apollonio, Massimiliano Caramia, Giuseppe F. Italiano
      Pages 201-213

    3. A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs

      • Tim Nieberg, Johann Hurink, Walter Kern
      Pages 214-221

    4. Tolerance Based Algorithms for the ATSP

      • Boris Goldengorin, Gerard Sierksma, Marcel Turkensteen
      Pages 222-234
Back to top

Other volumes

  1. Graph-Theoretic Concepts in Computer Science

Keywords

About this book

During its 30-year existence, the International Workshop on Graph-Theoretic Concepts in Computer Science has become a distinguished and high-quality computer science event. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can successfully be applied to v- ious areas of computer science and by exposing new theories emerging from applications. In this way, WG provides a common ground for the exchange of information among people dealing with several graph problems and working in various disciplines. Thereby, the workshop contributes to forming an interdis- plinary research community. The original idea of the Workshop on Graph-Theoretic Concepts in C- puter Science was ingenuity in all theoretical aspects and applications of graph concepts, wherever applied. Within the last ten years, the development has strengthened in particular the topic of structural graph properties in relation to computational complexity. This workshop has become pivotal for the c- munity interested in these areas.An aimspeci?c to the 30thWG was to support the central role of WG in both of the prementioned areas on the one hand and on the other hand to promote its originally broader scope. The 30th WG was held at the Physikzentrum Bad Honnef, which serves as the main meeting point of the German Physical Society. It o?ers a secluded setting for research conferences, seminars, and workshops, and has proved to be especiallystimulatingforfruitful discussions.Talksweregiveninthenewlecture hall with a modern double rear projection, interactive electronic board, and full video conferencing equipment.

Editors and Affiliations

  • Department of Computer Science, ETH Zurich, ETH Zentrum, Zurich, Switzerland

    Juraj Hromkovič

  • Department of Computer Science, RWTH Aachen, Chair of Computer Science III, Aachen, Germany

    Manfred Nagl

  • Department of Computer Science III, RWTH Aachen University, Aachen, Germany

    Bernhard Westfechtel

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation