Sunday, June 28
afternoon arrival, check-in, registration
19:00 - 21:00 welcome party


Monday, June 29
9:00 - 10:00 Sue Whitesides
    Intractability in Graph Drawing and Geometry: FPT approaches
10:00 - 10:30 coffee break
  Session A Session B
10:30 - 10:55 Paweł Gawrychowski and Travis Gagie
  Minimax Trees in Linear Time with Applications
10:55 - 11:20 Jan Kyncl, Josef Cibulka, Viola Meszaros, Pavel Valtr, and Rudolf Stolar
  Solution of Peter Winkler's Pizza Problem
11:20 - 11:45 Edyta Szymanska
  The Complexity of Almost Perfect Matchings in Uniform Hypergraphs with High Codegree
11:45 - 12:10 Darko Dimitrov, Tomáš Dvořák, Petr Gregor, and Riste Škrekovski
  Gray code compression
  lunch break
14:00 - 14:25 Christophe Crespelle and Philippe Gambette
  Efficient neighborhood encoding for interval graphs and permutation graphs and O(n) Breadth-First Search
Amihood Amir, Zvi Gotthilf, and B. Riva Shalom
  Weighted LCS
14:25 - 14:50 Evaggelos Lappas, Stavros Nikolopoulos, and Leonidas Palios
  An O(n)-time Algorithm for the Paired-Domination Problem on Permutation Graphs
Petr Prochazka and Jan Holub
  New Word-based Adaptive Dense Compressors
14:50 - 15:15 Tinaz Ekim, Pinar Heggernes, and Daniel Meister
  Polar permutation graphs
Tomohiro I, Satoshi Deguchi, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda
  Lightweight Parameterized Suffix Array Construction
15:15 - 15:40 N.R. Aravind and C. R. Subramanian
  Forbidden subgraph colorings and the oriented chromatic number
Kimmo Fredriksson and Szymon Grabowski
  Fast convolutions and their applications in approximate string matching
15:40 - 16:00 coffee break
16:00 - 16:25 Thomas Feierl
  The height and range of watermelons without wall
Sylwia Cichacz, Dalibor Fronček, and Petr Kovář
  Note on decomposition of Kn,n into (0,j)-prisms
16:25 - 16:50 Alexis Darrasse and Michele Soria
  Limiting distribution for distances in k-trees
Petr Kovář and Michael Kubesa
  Factorizations of complete graphs into spanning trees with all possible maximum degrees
17:00 - 18:30 problem session


Tuesday, June 30
9:00 - 10:00 Giovanni Manzini
    Succinct Representations of Trees
10:00 - 10:30 coffee break
10:30 - 10:55 Michael Drmota
  Embedded trees and the support of the ISE
10:55 - 11:20 Nicola Apollonio and Massimiliano Caramia
  Integrality properties of certain special balanceable clutters
11:20 - 11:45 Ingo Schiermeyer
  Rainbow connection in graphs with minimum degree three
11:45 - 12:10 Michael Drmota, Bernhard Gittenberger, and Reinhard Kutzelnigg
  Combinatorial Models for Cooperation Networks
  lunch break
14:00 - 16:00 castle tour
16:00 - 17:00 Jack Edmonds
    Branching Systems
17:30 - 18:30 chamber concert


Wednesday, July 1st
9:00 - 10:00 Robin Thomas
    Kt Minors in Large t-connected Graphs
10:00 - 10:30 coffee break
10:30 - 10:55 Vadim Lozin and Nicholas Korpelainen
  Bipartite Graphs of Large Clique-width
10:55 - 11:20 Petr Škoda
  Computability of Branch-width of Submodular Partition Functions
11:20 - 11:45 Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle
  Feedback vertex set on graphs of low cliquewidth
11:45 - 12:10 Robert Ganian and Petr Hliněný
  Better Polynomial Algorithms on Graphs of Bounded Rank-width
  lunch break
13:00 - 21:30 excursion & conference dinner


Thursday, July 2nd
9:00 - 10:00 Michael Fellows
    Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
10:00 - 10:30 coffee break
  Session A Session B
10:30 - 10:55 Peyman Nayeri, Charles Colbourn, and Goran Konjevod
  Randomized Postoptimization of Covering Arrays
10:55 - 11:20 Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen
  On the Maximal Number of Cubic Subwords in a String
11:20 - 11:45 Simone Faro, Matteo Campanelli, and Domenico Cantone
  A New Algorithm for Efficient Pattern Matching with Swaps
11:45 - 12:10 Maxime Crochemore, Lucian Ilie, Costas Iliopoulos, Marcin Kubica, Wojciech Rytter, and Tomasz Waleń
  LPF computation revisited
  lunch break
14:00 - 14:25 Gianlorenzo D'Angelo, Gabriele Di Stefano, and Alfredo Navarra
  Evaluation of recoverable-robust timetables on tree networks
Ľubomír Török and Imrich Vrťo
  Antibandwidth of d-dimensional meshes
14:25 - 14:50 Nicolas Bourgeois, Giorgio Lucarelli, Ioannis Milis, and Vangelis Paschos
  Approximating the max edge-coloring problem
Rinovia Simanjuntak, Hilda Assiyatun, Herolistya Baskoroputro, Hazrul Iswadi, Yudi Setiawan, and Saladdin Uttunggadewa
  Graphs with relatively constant metric dimension
14:50 - 15:15 Thirumala Reddy T V, Sai Krishna D, and Pandu Rangan C
  The Guarding Problem - Complexity and Approximation
Ling-Ju Hung, Ton Kloks, and Chuan Min Lee
  Trivially-Perfect Width
15:15 - 15:40 Hajo Broersma, Dieter Kratsch, and Gerhard Woeginger
  Fully decomposable split graphs
Paul Manuel, Indra Rajasingh, Bharati Rajan, and Joice Punitha
  Kernel in Circulant Graphs
15:40 - 16:00 coffee break
16:00 - 16:25 Carsten Gutwenger, Petra Mutzel, and Bernd Zey
  Planar Biconnectivity Augmentation With Fixed Embedding
Stéphane Bessy, Christophe Paul, and Anthony Perez
  Polynomial kernels for 3-leaf power edge modification problems
16:25 - 16:50 David Coudert, Frédéric Giroire, and Ignasi Sau
  Edge-Simple Circuits Through 10 Ordered Vertices in Square Grids
Daniel Lokshtanov, Saket Saurabh, and Somnath Sikdar
  Simpler Parameterized Algorithm for OCT
16:50 - 17:15 Marián Klešč
  The crossing numbers of Cartesian products of stars and graphs on five vertices
Hajo Broersma, Fedor Fomin, Daniel Paulusma, and Peter Golovach
  Three complexity results on coloring Pk-free graphs
  dinner & garden party



There will be a data projector available along with one laptop or PC. The participants can use their own laptops. We encourage everybody to test the compatibility of the equipment in advance.


List of accepted posters

There were 12 posters accepted (listed in the order they were received). The poster display will be during coffee breaks.

ID   Authors and title
103.   Travis Gagie, Gonzalo Navarro and Yakov Nekrich. Small Codes
104.   Travis Gagie, Simon Puglisi and Andrew Turpin. Another Virtue of Wavelet Trees
105.   Jurij Mihelic and Borut Robic. Flexible Selection of Attributes in Tree and General Scenario Graphs
106.   Reinhard Kutzelnigg. Cuckoo Hashing with a Stash and Random Graphs of Excess r
107.   Yoshimitsu Iwasaki. Solution for the Tower of Hanoi problem with four pegs
108.   Mark Korenblit and Vadim E. Levit. On Algebraic Expressions of Square Rhomboids
109.   Saeed Shahghobadi. A new polynomial dual network simplex algorithm
110.   Daniel Martin, Domingos Dellamonica and Vojtech Rodl. Subgraphs with large directed girth and large minimum out-degree
111.   Veronika Kraus. The degree distribution of unlabelled outerplanar graphs
112.   Bharati Rajan, Indra Rajasingh and Sonia Thomas. Conditional resolvability
113.   Zdeněk Dostál, Pavla Kabelíková, Petr Kovar and Tomáš Kozubek. Graph center, Perron vector and stable evaluation of a generalised inverse matrix
114.   Subramanian Aramugam. Equitable domination in graphs

contact Last update: 29.12.2011