List of accepted papers

The following 28 papers have been selected by the PC for presentation at WG 2009:

  • George Mertzios, Ignasi Sau and Shmuel Zaks.
    A New Intersection Model and Improved Algorithms for Tolerance Graphs
  • Lucia Draque Penso, Dieter Rautenbach and Jayme Luiz Szwarcfiter.
    Cycles, Paths, Connectivity and Diameter in Distance Graphs
  • Zhentao Li and Ignasi Sau.
    Graph Partitioning and Traffic Grooming with Bounded Degree Request Graph
  • Frank Kammer and Torsten Tholey.
    The k-Disjoint Path Problem on Chordal Graphs
  • Shiri Chechik and David Peleg.
    Low-Port Tree Representations
  • Torben Hagerup.
    An even simpler linear-time algorithm for verifying minimum spanning trees
  • Michael Fellows, Jiong Guo and Iyad Kanj.
    The Parameterized Complexity of Some Minimum Label Problems
  • Iyad Kanj, Andreas Wiese and Fenghui Zhang.
    Local Algorithms for Edge Colorings in UDGs
  • Shimon Shrem, Michal Stern and Martin Golumbic.
    Smallest Odd Holes in Claw-Free Graphs
  • Stéphane Grumbach and Zhilin Wu.
    Logical locality entails frugal distributed computation over graphs (extended abstract)
  • Bastian Katz, Ignaz Rutter and Gerhard Woeginger.
    An algorithmic study of switch graphs
  • Daniel Meister and Jan Arne Telle.
    Chordal digraphs
  • Yoshio Okamoto, Ryuhei Uehara and Takeaki Uno.
    Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes
  • Gary MacGillivray, André Raspaud and Jacobus Swarts.
    Injective Oriented Colourings
  • Rajiv Gandhi, Bradford Greening, Jr, Sriram Pemmaraju and Rajiv Raman.
    Sub-coloring and Hypocoloring Interval Graphs
  • Petr Golovach, Jan Kratochvil and Ondrej Suchy.
    Parameterized Complexity of Generalized Domination Problems
  • Mamadou Moustapha Kanté and Michaël Rao.
    Directed Rank-Width and Displit Decomposition
  • Ilia Averbouch, Johann Makowsky and Peter Tittmann.
    A Graph Polynomial Arising from Community Structure
  • Gruia Calinescu, Cristina Fernandes and Hemanshu Kaul.
    Maximum Series-Parallel Subgraph
  • Hajo Broersma, Fedor Fomin, Pim van 't Hof and Daniel Paulusma.
    Fast exact algorithms for hamiltonicity in claw-free graphs
  • Pim van 't Hof, Marcin Kaminski and Daniel Paulusma.
    Finding induced paths of given parity in claw-free graphs
  • Sebastian Ordyniak and Stephan Kreutzer.
    Distance d-Domination Games
  • Frank Gurski and Egon Wanke.
    On module-composed graphs
  • Christophe Crespelle.
    Fully Dynamic Representations of Interval Graphs
  • Fedor Fomin, Daniel Lokshtanov and Saket Saurabh.
    An Exact Algorithm for Minimum Distortion Embedding
  • René Sitters and Alexander Grigoriev.
    Connected feedback vertex set in planar graphs
  • Van Bang Le and Ngoc Tuy Nguyen.
    Hardness Results and Efficient Algorithms for Graph Powers
  • Henning Fernau, Serge Gaspers and Daniel Raible.
    Exact and Parameterized Algorithms for Max Internal Spanning Tree

Last update: 2009-06-16