Skip to main content
SpringerLink
Log in
Book cover

Graph-Theoretic Concepts in Computer Science

36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010, Revised Papers

  • Conference proceedings
  • © 2010

Overview

Editors:
  1. Dimitrios M. Thilikos

    1. Department of Mathematics, University of Athens, Athens, Greece

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

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

Included in the following conference series:

Conference proceedings info: WG 2010.

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. Invited Talks

    1. Algorithmic Barriers from Phase Transitions in Graphs

      • Dimitris Achlioptas
      Pages 1-1

    2. Algorithmic Graph Minors and Bidimensionality

      • Erik D. Demaine
      Pages 2-2

  3. Regular Talks

    1. Complexity Results for the Spanning Tree Congestion Problem

      • Yota Otachi, Hans L. Bodlaender, Erik Jan van Leeuwen
      Pages 3-14

    2. max-cut and Containment Relations in Graphs

      • Marcin Kamiński
      Pages 15-26

    3. The Longest Path Problem is Polynomial on Cocomparability Graphs

      • Kyriaki Ioannidou, Stavros D. Nikolopoulos
      Pages 27-38

    4. Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds

      • Petr A. Golovach, Dieter Kratsch, Jean-Francois Couturier
      Pages 39-50

    5. On Stable Matchings and Flows

      • Tamás Fleiner
      Pages 51-62

    6. Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs

      • Hajo Broersma, Petr A. Golovach, Daniël Paulusma, Jian Song
      Pages 63-74

    7. Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time

      • Pinar Heggernes, Pim van ’t Hof, Daniel Lokshtanov, Jesper Nederlof
      Pages 75-87

    8. Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching

      • Mathieu Liedloff, Ioan Todinca, Yngve Villanger
      Pages 88-99

    9. Efficient Algorithms for Eulerian Extension

      • Frederic Dorn, Hannes Moser, Rolf Niedermeier, Mathias Weller
      Pages 100-111

    10. On the Small Cycle Transversal of Planar Graphs

      • Ge Xia, Yong Zhang
      Pages 112-122

    11. Milling a Graph with Turn Costs: A Parameterized Complexity Perspective

      • Mike Fellows, Panos Giannopoulos, Christian Knauer, Christophe Paul, Frances Rosamond, Sue Whitesides et al.
      Pages 123-134

    12. Graphs that Admit Right Angle Crossing Drawings

      • Karin Arikushi, Radoslav Fulek, Baláazs Keszegh, Filip Morić, Csaba D. Tóth
      Pages 135-146

    13. Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs

      • Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
      Pages 147-158

    14. On the Boolean-Width of a Graph: Structure and Applications

      • Isolde Adler, Binh-Minh Bui-Xuan, Yuri Rabinovich, Gabriel Renault, Jan Arne Telle, Martin Vatshelle
      Pages 159-170

    15. Generalized Graph Clustering: Recognizing (p,q)-Cluster Graphs

      • Pinar Heggernes, Daniel Lokshtanov, Jesper Nederlof, Christophe Paul, Jan Arne Telle
      Pages 171-183

    16. Colouring Vertices of Triangle-Free Graphs

      • Konrad Dabrowski, Vadim Lozin, Rajiv Raman, Bernard Ries
      Pages 184-195

    17. A Quartic Kernel for Pathwidth-One Vertex Deletion

      • Geevarghese Philip, Venkatesh Raman, Yngve Villanger
      Pages 196-207
Back to top

Other volumes

  1. Graph Theoretic Concepts in Computer Science

Keywords

About this book

The 36th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2010) took place in Zar´ os, Crete, Greece, June 28–30, 2010. About 60 mathematicians and computer scientists from all over the world (Australia, Canada, Czech Republic, France, Germany, Greece, Hungary, Israel, Japan, The Netherlands, Norway, Poland, Switzerland, the UK, and the USA) attended the conference. WG has a long tradition. Since 1975, WG has taken place 21 times in Germany, four times in The Netherlands, twice in Austria, twice in France and once in the Czech Republic, Greece, Italy, Norway, Slovakia, Switzerland, and the UK. WG aims at merging theory and practice by demonstrating how concepts from graph theory can be applied to various areas in computer science, or by extracting new graph theoretic problems from applications. The goal is to presentemergingresearchresultsand to identify and exploredirections of future research.The conference is well-balanced with respect to established researchers and young scientists. There were 94 submissions, two of which where withdrawn before entering the review process. Each submission was carefully reviewed by at least 3, and on average 4.5, members of the Program Committee. The Committee accepted 28 papers, which makes an acceptance ratio of around 30%. I should stress that, due to the high competition and the limited schedule, there were papers that were not accepted while they deserved to be.

Editors and Affiliations

  • Department of Mathematics, University of Athens, Athens, Greece

    Dimitrios M. Thilikos

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation