Skip to main content
SpringerLink
Log in

Graph-Theoretic Concepts in Computer Science

33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers

  • Conference proceedings
  • © 2007

Overview

Editors:
  1. Andreas Brandstädt
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Dieter Kratsch
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Haiko Müller
    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 4769)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: WG 2007.

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

  1. Front Matter

    Download chapter PDF

  2. Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs

    • Petr Golovach, Jan Kratochvíl
    Pages 1-11

  3. Recognizing Bipartite Tolerance Graphs in Linear Time

    • Arthur H. Busch, Garth Isaak
    Pages 12-20

  4. Graph Searching in a Crime Wave

    • David Richerby, Dimitrios M. Thilikos
    Pages 21-32

  5. Monotonicity of Non-deterministic Graph Searching

    • Frédéric Mazoit, Nicolas Nisse
    Pages 33-44

  6. Tree-Width and Optimization in Bounded Degree Graphs

    • Vadim Lozin, Martin Milanič
    Pages 45-54

  7. On Restrictions of Balanced 2-Interval Graphs

    • Philippe Gambette, Stéphane Vialette
    Pages 55-65

  8. Graph Operations Characterizing Rank-Width and Balanced Graph Expressions

    • Bruno Courcelle, Mamadou Moustapha Kanté
    Pages 66-75

  9. The Clique-Width of Tree-Power and Leaf-Power Graphs

    • Frank Gurski, Egon Wanke
    Pages 76-85

  10. NLC-2 Graph Recognition and Isomorphism

    • Vincent Limouzy, Fabien de Montgolfier, Michaël Rao
    Pages 86-98

  11. A Characterisation of the Minimal Triangulations of Permutation Graphs

    • Daniel Meister
    Pages 99-108

  12. The 3-Steiner Root Problem

    • Maw-Shang Chang, Ming-Tat Ko
    Pages 109-120

  13. On Finding Graph Clusterings with Maximum Modularity

    • Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Görke, Martin Hoefer, Zoran Nikoloski et al.
    Pages 121-132

  14. On Minimum Area Planar Upward Drawings of Directed Trees and Other Families of Directed Acyclic Graphs

    • Fabrizio Frati
    Pages 133-144

  15. A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs

    • Torben Hagerup
    Pages 145-150

  16. Approximation Algorithms for Geometric Intersection Graphs

    • Klaus Jansen
    Pages 151-153

  17. An Equivalent Version of the Caccetta-Häggkvist Conjecture in an Online Load Balancing Problem

    • Angelo Monti, Paolo Penna, Riccardo Silvestri
    Pages 154-165

  18. Mixing 3-Colourings in Bipartite Graphs

    • Luis Cereceda, Jan van den Heuvel, Matthew Johnson
    Pages 166-177

  19. Minimum-Weight Cycle Covers and Their Approximability

    • Bodo Manthey
    Pages 178-189

  20. On the Number of α-Orientations

    • Stefan Felsner, Florian Zickfeld
    Pages 190-201
Back to top

Other volumes

  1. Graph-Theoretic Concepts in Computer Science

Keywords

About this book

The 33rd International Conference “Workshop on Graph-Theoretic Concepts in Computer Science” (WG 2007) took place in the Conference Center in old castleinDornburgnearJena,Germany,June21–23,2007.Theapproximately80 participants came from various countries all over the world, among them Brazil, Canada, the Czech Republic, France, UK, Greece, Hungary, Italy, Japan, The Netherlands, Norway, Sweden, Taiwan, and the USA. WG 2007 continued the series of 32 previous WG conferences. Since 1975, the WG conference has taken place 20 times in Germany, four times in The Netherlands, twice in Austria as well as once in Italy, Slovakia, Switzerland, the Czech Republic, France and in Norway. The WG conference traditionally 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 researchresults and to identify and exploredirections of future research. Thecontinuinginterestinthe WGconferenceswasre?ectedin thehighn- ber of submissions; 99 papers were submitted and in an evaluation process with four reports per submission, 30 papers were accepted by the Program Comm- tee for the conference. Due to the high number of submissions and the limited schedule of 3 days, various good papers could not be accepted. There were invited talks by Ming-Yang Kao (Evanston, Illinois) on algori- mic DNA assembly, and by Klaus Jansen (Kiel, Germany) on approximation algorithms for geometric intersection graphs.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation