WG 2010 Accepted Papers


Yota Otachi, Hans L. Bodlaender and Erik Jan van Leeuwen.Complexity Results for the Spanning Tree Congestion Problem

Marcin Kaminski. Max-Cut and containment relations in graphs

Stavros Nikolopoulos and Kyriaki Ioannidou.
The Longest Path Problem is Polynomial on Cocomparability Graphs

Petr Golovach, Dieter Kratsch and Jean-Francois Couturier.
Colorings With Few Colors: Counting, Enumeration and Combinatorial Bounds

Tamas Fleiner.
On stable matchings and flows

Hajo Broersma, Petr Golovach, Daniel Paulusma and Jian Song.
Narrowing down the gap on the complexity of coloring P_k-free graphs

Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov and Jesper Nederlof.
Computing the cutwidth of bipartite permutation graphs in linear time

Mathieu Liedloff, Ioan Todinca and Yngve Villanger.
Solving Capacitated Dominating Set by using Covering by Subsets and Maximum Matching

Frederic Dorn, Hannes Moser, Rolf Niedermeier and Mathias Weller.
Efficient Algorithms for Eulerian Extension

Ge Xia and Yong Zhang.
On the Small Cycle Transversal of Planar Graphs

Panos Giannopoulos, Christian Knauer, Mike Fellows, Christophe Paul, Frances Rosamond, Sue Whitesides and Nathan Yu.
Milling a Graph with Turn Costs: a Parameterized Complexity Perspective

Karin Arikushi, Radoslav Fulek, Balazs Keszegh, Filip Moric and Csaba Toth.
Drawing Graphs with Orthogonal Crossings

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk and Jakub Wojtaszczyk.
Kernelization hardness of connectivity problems in d-degenerate graphs

Isolde Adler, Binh-Minh Bui-Xuan, Yuri Rabinovich, Gabriel Renault, Jan Arne Telle and Martin Vatshelle.
On the boolean-width of a graph: structure
and applications

Pinar Heggernes, Daniel Lokshtanov, Jesper Nederlof, Christophe Paul and Jan Arne Telle.
Generalized graph clustering: recognizing (p,q)-cluster graphs

Konrad Dabrowski, Vadim Lozin, Rajiv Raman and Bernard Ries.
Colouring vertices of triangle-free graphs

Geevarghese Philip, Venkatesh Raman and Yngve Villanger.
A Quartic Kernel for Pathwidth-One Vertex Deletion

Jeremie Chalopin, Paola Flocchini, Bernard Mans and Nicola Santoro.
Network Exploration  by Silent and Oblivious Robots

Annabell Berger and Matthias Müller-Hannemann.
Uniform Sampling of Undirected and Directed Graphs with a Fixed Degree Sequence

René van Bevern, Christian Komusiewicz, Hannes Moser and Rolf Niedermeier.
Measuring Indifference: Unit Interval Vertex Deletion

Dániel Marx and Ildikó Schlotter.
Parameterized Complexity of the Arc-Preserving Subsequence Problem

Steven Chaplick, Marisa Gutierrez, Benjamin Lévêque and Silvia Tondato.
From path graphs to directed path graphs

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse and David Ilcinkas.
Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces

Robert Elsaesser and Adrian Ogierman.
Efficient Broadcasting in Random Power Law Networks

Padmini Mukkamala, Janos Pach and Deniz Sarioz.
Graphs with large obstacle numbers

Edyta Szymanska
.
The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Codegree

Colin McDiarmid and Tobias Mueller.
The number of bits needed to represent a unit disk graph

Jannik Matuschke and Britta Peis.
Lattices and maximum flow algorithms in planar graphs