Program

Monday, 26 July 2010

8:30-9:15 Registration
9:15-9:30 Welcome from the organizers
Invited Talk
9:30-10:30 Mirka Miller:
Constructions of Large Graphs and Digraphs of Given Diameter and Maximum Degree
10:30-11:00 Coffee break
Session on Graph theory and graph algorithms
11:00-11:20 Jan Kratochvil, Boris Horvat and Tomaz Pisanski:
On the Computational Complexity of Degenerate Unit Distance Representations of Graphs
11:20-11:40 Joe Ryan, Oudone Phanalasy, Mirka Miller and Leanne Rylands:
On Antimagic Labeling for Generalized Web and Flower Graphs
11:40-12:00 Alfredo Navarra and Cristina M. Pinotti:
Collision-free Routing in Sink-Centric Sensor Networks with Coarse-Grain Coordinates
12:00-12:20 Ferdinando Cicalese and Martin Milanic:
Graphs of separability at most two: structural characterizations and their consequences
13:00-14:00 Lunch
Invited Talk
14:30-15:30 Dorothea Wagner:
Clustering of Static and Temporal Graphs
First poster session
15:30-16:00 First poster session and coffee break
Session on Polynomial-time graph and hypergraph algorithms
16:00-16:20 Ulrik Brandes, Sabine Cornelsen, Barbara Pampel and Arnaud Sallaberry:
Path-Based Supports for Hypergraphs
16:20-16:40 Pinar Heggernes, Pim van 't Hof and Daniel Paulusma:
Computing role assignments of proper interval graphs in polynomial time
16:40-17:00 Ulrik Brandes, Sabine Cornelsen, Barbara Pampel and Arnaud Sallaberry:
Hypergraphs and Outerplanarity
17:00-17:20 Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani and Ignaz Rutter:
Testing the Simultaneous Embeddability of Two Graphs whose Intersection is a Biconnected Graph or a Tree

Tuesday, 27 July 2010

Invited Talk
9:00-10:00 Alan Frieze:
The Karp-Sipser Matching Algorithm and Refinements
10:00-10:20 Coffee break
Session on Random processes and randomized algorithms
10:20-10:40 Tugkan Batu, Petra Berenbrink and Colin Cooper:
Chains-into-Bins Processes
10:40-11:00 Mohammed Abdullah, Colin Cooper and Tomasz Radzik:
The Cover time of Cartesian Product Graphs
11:00-11:20 Prosenjit Bose, Karim Douieb and Pat Morin:
Skip Lifts: A Probabilistic Alternative to Red-Black Trees
11:20-11:30 Break
Session on Fixed-parameter tractability
11:30-11:50 Konrad Dabrowski, Vadim Lozin, Haiko Muller and Dieter Rautenbach:
Parameterized Algorithms for the Independent Set Problem in Hereditary Graph Classes
11:50-12:10 Riccardo Dondi, Paola Bonizzoni, Gianluca Della Vedova and Yuri Pirola:
Parameterized Complexity of k-Anonymity: Hardness and Tractability
12:10-12:30 Geevarghese Philip, Henning Fernau, Fedor V. Fomin, Saket Saurabh, Daniel Lokshtanov and Matthias Mnich:
Ranking and Drawing in Subexponential Time
13:00-14:00 Lunch
Session on Patterns in trees and pyramid pebbling
14:30-14:50 Julien Allali, Cedric Chauve, Pascal Ferraro and Anne-Laure Gaillard:
Efficient chaining of seeds in ordered trees
14:50-15:10 Yusaku Kaneta and Hiroki Arimura:
Faster Bit-Parallel Algorithms for Unordered Pseudo-Tree Matching and Tree Homeomorphism
15:10-15:30 Desh Ranjan, John Savage and Mohammad Zubair:
Upper and Lower I/O bounds for pebbling r-pyramids
15:30-15:45 Coffee break
Problem session
15:45-16:45 Problem session
Boat trip and dinner
17:45-21:00 Boat trip and dinner

Wednesday, 28 July 2010

Invited Talk
9:00-10:00 Gregory Kucherov:
Seeding methods for biosequence search: algorithmic ideas and applications
10:00-10:20 Coffee break
Session on Strings
10:20-10:40 Ferdinando Cicalese, Peter Erdos and Zsuzsanna Liptak:
Efficient Reconstruction of RC-Equivalent Strings
10:40-11:00 Gregory Kucherov, Tamar Pinhas and Michal Ziv-Ukelson:
Regular Expression Constrained Sequence Alignment Revisited
11:00-11:20 Djamal Belazzougui:
Worst case efficient single and multiple string matching in the RAM model
11:20-11:30 Break
Session on Strings
11:30-11:50 Maxime Crochemore, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter and Tomasz Walen:
On the Maximal Sum of Exponents of Runs in a String
11:50-12:10 Francine Blanchet-Sadri, Bob Chen and Aleksandar Chakarov:
Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three
12:10-12:30 Maxime Crochemore, Laura Giambruno, Alessio Langiu, Filippo Mignosi and Antonio Restivo:
Dictionary-Symbolwise Flexible Parsing
13:00-14:00 Lunch
Session on Complexity: boundary between NP-hardness and polynomial time
14:30-14:50 Hajo Broersma, Paul Bonsma, Viresh Patel and Artem Pyatkin:
The complexity status of problems related to sparsest cuts
14:50-15:10 Marek Tesar and Bernard Lidicky:
Complexity of locally injective homomorphism to the Theta graphs
15:10-15:30 Cristina Bazgan, Sonia Toubaline and Zsolt Tuza:
Complexity of most vital nodes for Independent Set on tree structures
15:30-15:50 Marcin Kaminski, Paul Medvedev and Martin Milanic:
Shortest paths between shortest paths and independent sets
Second poster session
15:50-16:15 Second poster session and coffee break
Session on Graph algorithms and computational geometry
16:15-16:35 Tomas Dvorak, Jiri Fink, Petr Gregor and Vaclav Koubek:
Efficient connectivity testing of hypercubic networks with faults
16:35-16:55 Danny Z. Chen and Haitao Wang:
Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures
16:55-17:15 Martin Kochol, Nada Krivonakova, Silvia Smejova and Katarina Horvathova:
Reductions of Matrices Associated with Nowhere-Zero Flows
17:15-17:35 Martin Kochol and Riste Skrekovski:
Dichotomy for Coloring of Dart Graphs