Program: WG2011

Scientific and social program

9:00 Invited talk A. Matchetti-Spaccamela: Structures and Hyperstructures in Metabolic Networks
10:00 Cofee Break
10:30 – 10:55 Marek Cygan, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk and Ildiko Schlotter. Parameterized Complexity of Eulerian Deletion Problems
11:00 – 11:25 Manuel Sorge, René Van Bevern, Rolf Niedermeier and Mathias Weller. From Few Components to an Eulerian Graph by Adding Arcs
11:30 – 11:55 Daniel Lokshtanov, Matthias Mnich and Saket Saurabh. Planar k-Path in Subexponential Time and Polynomial Space
12:00 – 12:25 Toru Hasunuma and Hiroshi Nagamochi. Improved Bounds for Minimum Fault- Tolerant Gossip Graphs
12:30 Lunch
14:00 -14:25 Andrew McGrae and Michele Zito. Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem
14:30 -14:55 Jean-Francois Couturier, Petr Golovach, Dieter Kratsch and Daniel Paulusma. List coloring in the absence of a linear forest
15:00 – 15:25 Ondřej Bílka, Jozef Jirásek, Pavel Klavík, Martin Tancer and Jan Volec. On the Complexity of Planar Covering of Small Graphs
15:30 Coffee Break
16:00 -16:25 Felix Arends, Joel Ouaknine and Charles Wampler. On Searching for Small Kochen-Specker Vector Systems
16:30 -16:55 Michael Pelsmajer, Marcus Schaefer, Daniel Štefankovie and Radoslav Fulek. Hanani-Tutte and Monotone Drawings
17:00 -17:25 Christopher Auer and Andreas Gleißner. Characterizations of Deque and Queue Graphs
18:00 Dinner

9:00 – 9:25 Rémy Belmonte and Martin Vatshelle. Graph Classes with Structured Neighborhoods and Algorithmic Applications
9:30 – 9:55 Hisao Tamaki. A polynomial time algorithm for bounded directed pathwidth
10:00 -10:25 Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno and Koichi Yamazaki. Approximability of the Path-Distance-Width for AT-free Graphs
10:30 Coffee Break
11:00 -11:25 Konstanty Junosza-Szaniawski, Zbigniew Lonc and Michal Tuczynski. Counting independent sets in claw-free graphs
11:30 – 11:55 Christine Cheng, Eric McDermid and Ichiro Suzuki. Planarization and acyclic
colorings of subcubic claw-free graphs
12:00 – 12:55 Iyad Kanj and Fenghui Zhang. On the independence number of graphs with maximum degree 3
12:30 Lunch
14:00 Monastery sightseeing tour
15:30 Coffee Break
16:00 -16:25 Liliana Alcon, Luerbio Faria, Celina Figueiredo and Marisa Gutierrez. Split clique graph complexity
16:30 -16:55 Serge Gaspers, Mathieu Liedloff, Maya Stein and Karol Suchan. Complexity of Splits Reconstruction for Low-Degree Trees
17:00 -17:25 Marijke Bodlaender, Cor Hurkens and Gerhard J. Woeginger. The Cinderella game on holes and anti-holes
17:30 -17:55 Hans L. Bodlaender and Dieter Kratsch. Exact Algorithms for Kayles
18:30 Concert
20:00 Banquet

9:00 Invited talk D. Marx: Important Separators and Parameterized Algorithms
10:00 Cofee Break
10:30 -10:55 Andreas Emil Feldmann, Shantanu Das and Peter Widmayer. Restricted Cuts for Bisections in Solid Grids
11:00 -11:25 Juraj Stacho, Elad Cohen and Steven Chaplick. Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid
11:30 – 11:55 Holger Flier, Matus Mihalak, Anna Zych and Peter Widmayer. Maximum
Independent Set in 2-Direction Outersegment Graphs
12:00 -12:25 Alexander Ravsky and Oleg Verbitsky. On collinear sets in straight line drawings
12:30 Lunch
14:00 -14:25 Katarina Cechlarova and Eva Jelínková. Approximability of Economic Equilibrium for Housing Markets With Duplicate Houses
14:30 -14:55 Danny Hermelin, Chien-Chung Huang, Stefan Kratsch and Magnus Wahlström. Parameterized Two-Player Nash Equilibrium
15:00 -15:25 Ján Katrenič, František Galčík and Gabriel Semanišin. On computing an optimal semi-matching
15:30 – 15:55 Magnus M. Halldorsson, Sergey Kitaev and Artem Pyatking. Alternation graphs
16:00 Coffee Break
17:00 Departure (from Tepla) of the bus to Prague, expected arrival to Prague – 19:00
18:00 Dinner

10:00 The Bečov castle Sightseeing Tour
13:00 Lunch at the family brewery Chodovar
15:00 Brewery tour
17:00 Departure (from Chodovar) of the bus to Prague, expected arrival to Prague – 19:00

This program is also available for download as a PDF file.