Skip to main content
SpringerLink
Log in

Graph-Theoretic Concepts in Computer Science

35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009, Revised Papers

  • Conference proceedings
  • © 2010

Overview

Editors:
  1. Christophe Paul

    1. CNRS - LIRMM, Montpellier Cedex 5, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Michel Habib

    1. LIAFA, case 7014, Université Paris Diderot, Paris Cedex 13, France

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

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

Included in the following conference series:

Conference proceedings info: WG 2009.

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

  1. Front Matter

    Download chapter PDF

  2. Graph-Theoretic Solutions to Computational Geometry Problems

    • David Eppstein
    Pages 1-16

  3. Algorithms for Classes of Graphs with Bounded Expansion

    • Zdeněk Dvořák, Daniel Král’
    Pages 17-32

  4. A Graph Polynomial Arising from Community Structure (Extended Abstract)

    • Ilia Averbouch, Johann A. Makowsky, Peter Tittmann
    Pages 33-43

  5. Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs

    • Hajo Broersma, Fedor V. Fomin, Pim van ’t Hof, Daniël Paulusma
    Pages 44-53

  6. Maximum Series-Parallel Subgraph

    • Gruia Călinescu, Cristina G. Fernandes, Hemanshu Kaul
    Pages 54-65

  7. Low-Port Tree Representations

    • Shiri Chechik, David Peleg
    Pages 66-76

  8. Fully Dynamic Representations of Interval Graphs

    • Christophe Crespelle
    Pages 77-87

  9. The Parameterized Complexity of Some Minimum Label Problems

    • Michael R. Fellows, Jiong Guo, Iyad A. Kanj
    Pages 88-99

  10. Exact and Parameterized Algorithms for Max Internal Spanning Tree

    • Henning Fernau, Serge Gaspers, Daniel Raible
    Pages 100-111

  11. An Exact Algorithm for Minimum Distortion Embedding

    • Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh
    Pages 112-121

  12. Sub-coloring and Hypo-coloring Interval Graphs

    • Rajiv Gandhi, Bradford Greening Jr., Sriram Pemmaraju, Rajiv Raman
    Pages 122-132

  13. Parameterized Complexity of Generalized Domination Problems

    • Petr A. Golovach, Jan Kratochvíl, Ondřej Suchý
    Pages 133-142

  14. Connected Feedback Vertex Set in Planar Graphs

    • Alexander Grigoriev, René Sitters
    Pages 143-153

  15. Logical Locality Entails Frugal Distributed Computation over Graphs (Extended Abstract)

    • Stéphane Grumbach, Zhilin Wu
    Pages 154-165

  16. On Module-Composed Graphs

    • Frank Gurski, Egon Wanke
    Pages 166-177

  17. An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees

    • Torben Hagerup
    Pages 178-189

  18. The k-Disjoint Paths Problem on Chordal Graphs

    • Frank Kammer, Torsten Tholey
    Pages 190-201

  19. Local Algorithms for Edge Colorings in UDGs

    • Iyad A. Kanj, Andreas Wiese, Fenghui Zhang
    Pages 202-213

  20. Directed Rank-Width and Displit Decomposition

    • Mamadou Moustapha Kanté, Michaël Rao
    Pages 214-225
Back to top

Other volumes

  1. Graph-Theoretic Concepts in Computer Science

Keywords

About this book

The 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009) took place at Montpellier (France), June 24–26 2009. About 80 computer scientists from all over the world (Australia, Belgium, Canada, China, Czech Republic, France, Germany, Greece, Israel, Japan, Korea, The Netherlands, Norway, Spain, UK, USA) attended the conference. Since1975,ithastakenplace20timesinGermany,fourtimesinTheNeth- lands, twice in Austria, as well as once in Italy, Slovakia, Switzerland, the Czech Republic, France, Norway, and the UK. The conference 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 appli- tions. The goal is to present recent research results and to identify and explore directions of future research. The conference is well-balanced with respect to established researchers and young scientists. There were 69 submissions. Each submission was reviewed by at least three, and on average four, Program Committee members. The Committee decided to accept 28 papers. Due to the competition and the limited schedule, some good papers could not be accepted. Theprogramalsoincludedexcellentinvitedtalks:onegivenbyDanielKràlon “AlgorithmsforClassesofGraphswithBoundedExpansion,” the otherbyDavid Eppsteinon“Graph-TheoreticSolutionstoComputationalGeometryProblems.” The proceedings contains two survey papers on these topics.

Editors and Affiliations

  • CNRS - LIRMM, Montpellier Cedex 5, France

    Christophe Paul

  • LIAFA, case 7014, Université Paris Diderot, Paris Cedex 13, France

    Michel Habib

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation