Skip to main content
SpringerLink
Log in

Graph-Theoretic Concepts in Computer Science

34th International Workshop, WG 2008, Durham, UK, June 30 -- July 2, 2008, Revised Papers

  • Conference proceedings
  • © 2008

Overview

Editors:
  1. Hajo Broersma

    1. Department of Computer Science, Durham University, Durham, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Thomas Erlebach

    1. Department of Computer Science, University of Leicester, Leicester, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Tom Friedetzky

    1. Department of Computer Science, Durham University, Durham, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Daniel Paulusma

    1. Department of Computer Science, Durham University, Durham, UK

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

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

Included in the following conference series:

Conference proceedings info: WG 2008.

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 Contributions

    1. (Un)-Stable Routing in the Internet: A Survey from the Algorithmic Perspective

      • Luca Cittadini, Giuseppe Di Battista, Massimo Rimondini
      Pages 1-13

    2. Memory Efficient Anonymous Graph Exploration

      • Leszek Gąsieniec, Tomasz Radzik
      Pages 14-29

    3. Algorithmic Meta Theorems

      • Martin Grohe
      Pages 30-30

  3. Regular Papers

    1. A Most General Edge Elimination Polynomial

      • Ilia Averbouch, Benny Godlin, Johann A. Makowsky
      Pages 31-42

    2. Approximating the Metric TSP in Linear Time

      • Davide Bilò, Luca Forlizzi, Guido Proietti
      Pages 43-54

    3. The Valve Location Problem in Simple Network Topologies

      • Hans L. Bodlaender, Alexander Grigoriev, Nadejda V. Grigorieva, Albert Hendriks
      Pages 55-65

    4. A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs

      • Paul Bonsma, Florian Zickfeld
      Pages 66-77

    5. On the Pseudo-achromatic Number Problem

      • Jianer Chen, Iyad A. Kanj, Jie Meng, Ge Xia, Fenghui Zhang
      Pages 78-89

    6. Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings

      • Pilu Crescenzi, Miriam Di Ianni, Federico Greco, Gianluca Rossi, Paola Vocca
      Pages 90-100

    7. Faster Exact Bandwidth

      • Marek Cygan, Marcin Pilipczuk
      Pages 101-109

    8. Additive Spanners for Circle Graphs and Polygonal Graphs

      • Feodor F. Dragan, Derek G. Corneil, Ekkehard Köhler, Yang Xiang
      Pages 110-121

    9. Upward Straight-Line Embeddings of Directed Graphs into Point Sets

      • Alejandro Estrella-Balderrama, Fabrizio Frati, Stephen G. Kobourov
      Pages 122-133

    10. Complexity of the Packing Coloring Problem for Trees

      • Jiří Fiala, Petr A. Golovach
      Pages 134-145

    11. Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges

      • J. Joseph Fowler, Michael Jünger, Stephen Kobourov, Michael Schulz
      Pages 146-158

    12. A Lower Bound on the Area Requirements of Series-Parallel Graphs

      • Fabrizio Frati
      Pages 159-170

    13. On Independent Sets and Bicliques in Graphs

      • Serge Gaspers, Dieter Kratsch, Mathieu Liedloff
      Pages 171-182

    14. Evaluations of Graph Polynomials

      • Benny Godlin, Tomer Kotek, Johann A. Makowsky
      Pages 183-194

    15. Parameterized Complexity for Domination Problems on Degenerate Graphs

      • Petr A. Golovach, Yngve Villanger
      Pages 195-205

    16. An Algorithm for Finding Input-Output Constrained Convex Sets in an Acyclic Digraph

      • Gregory Gutin, Adrian Johnstone, Joseph Reddington, Elizabeth Scott, Anders Yeo
      Pages 206-217
Back to top

Other volumes

  1. Graph-Theoretic Concepts in Computer Science

Keywords

About this book

The 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008) took place in Van Mildert College at Durham University, UK, 30 June – 2 July 2008. The approximately 80 participants came from va- ous countries all over the world, among them Australia, Brazil, Canada, Chile, Czech Republic, France, Greece, Hungary,Israel, Italy, Japan, The Netherlands, Norway, Poland, Spain, Switzerland, UK and the USA. WG 2008 continued the series of 33 previous WG conferences. Since 1975, the WG conference has taken place 21 times in Germany, four times in The Netherlands, twice in Austria as well as once in Italy, Slovakia, Switzerland, the Czech Republic, France, Norway and now in the UK. 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. The continuing interest in the WG conferences was re?ected in the number and quality of submissions; 76 papers were submitted and in an evaluation p- cess with four reports per submission, 30 papers were accepted by the Program Committee for the conference. Due to the high number of submissions and the limited schedule of 3 days, various good papers could not be accepted. Therewereexcellent invited talks by Giuseppe Di Battista(UniversitàRoma Tre,Italy)onalgorithmicaspectsof(un)-stableroutingintheInternet,byLeszek G?sieniec (University of Liverpool, UK) on memory-e?cient graph exploration, andbyMartinGrohe(Humboldt-UniversitätzuBerlin,Germany)onalgorithmic meta theorems.

Editors and Affiliations

  • Department of Computer Science, Durham University, Durham, UK

    Hajo Broersma, Tom Friedetzky, Daniel Paulusma

  • Department of Computer Science, University of Leicester, Leicester, UK

    Thomas Erlebach

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation