Monday, June 22th

8:45-9:20 Registration

9:20-9:30 Opening

String compression Chair: Gregory Kucherov

9:30-10:00 Quasi-Distinct Parsing and Optimal Compression Methods
Amihood Amir, Yonatan Aumann, Avivit Levy and Yuri Roshko

10:00-10:30 Generalized Substring Compression
Orgad Keller, Tsvi Kopelowitz, Shir Landau and Moshe Lewenstein

10:30-11:00 Coffee break

Invited Talk Chair: Maxime Crochemore

11:00-12:00 Text Indexing, Suffix Sorting and Data Compression: Common Problems and Techniques
Roberto Grossi

Index structures Chair: Maxime Crochemore

12:00-12:30 Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure
Andrzej Ehrenfeucht, Ross McConnell and Sung-Whan Woo

12:30-13:00 Linear Time Suffix Array Construction Using D-Critical Substrings
Ge Nong, Sen Zhang and Wai Hong Chan

13:00-14:30 Lunch

Data compression. Common subsequences and superstrings Chair: Amihood Amir

14:30-15:00 On the Value of Multiple Read/Write Streams for Data Compression
Travis Gagie

15:00-15:30 Reoptimization of the Shortest Common Superstring Problem
Davide Bilò, Hans-Joachim Boeckenhauer, Dennis Komm, Richard Kralovic, Tobias Moemke, Sebastian Seibert and Anna Zych

15:30-16:00 LCS Approximation via Embedding into Local Non-Repetitive Strings
Gad M. Landau, Avivit Levy and Ilan Newman

16:00-16:30 Coffee break

String and image matching Chair: Raphael Clifford

16:30-17:00 An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings
Simone Faro and Thierry Lecroq

17:00-17:30 Fast Searching in Packed Strings
Philip Bille

17:30-18:00 New Complexity Bounds for Image Matching under Rotation and Scaling
Christian Hundt and Maciej Liskiewicz

19:30 Conference dinner - Musée des Beaux-Arts

Tuesday, June 23th

Approximate string matching Chair: Gad Landau

9:00-9:30 Online Approximate Matching with Non-Local Distances
Benjamin Sach and Raphael Clifford

9:30-10:00 Optimal Edit Distance “1” Dictionary
Djamal Belazzougui

10:00-10:30 Approximate Matching for Run-Length Encoded Strings is 3Sum-Hard
Kuan-Yu Chen, Ping-Hui Hsu and Kun-Mao Chao

10:30-11:00 Coffee break

Invited talk Chair: Ricardo Baeza-Yates

11:00-12:00 Modeling and Algorithmic Challenges in Online Social Networks
Ravi Kumar

String algorithms Chair: Ricardo Baeza-Yates

12:00-12:30 Permuted Longest-Common-Prefix Array
Juha Karkkainen, Giovanni Manzini and Simon Puglisi

12:30-13:00 Periodic String Comparison
Alexander Tiskin

13:00-14:30 Lunch

Parametrized complexity Chair: Moshe Lewenstein

14:30-15:00 Deconstructing Intractability—A Case Study for Interval Constrained Coloring
Christian Komusiewicz, Rolf Niedermeier and Johannes Uhlmann

15:00-15:30 Maximum Motif Problem in Vertex-Colored Graphs
Dondi Riccardo, Fertin Guillaume and Stéphane Vialette

Social program

Wednesday, June 24th

Bioinformatics: RNA and networks Chair: Hélène Touzet

9:00-9:30 Fast RNA Structure Alignment for Crossing Input Structures
Rolf Backofen, Gad M. Landau, Mathias Möhl, Dekel Tsur and Oren Weimann

9:30-10:00 Sparse RNA folding: time and space efficient algorithms
Rolf Backofen, Dekel Tsur, Shay Zakov and Michal Ziv-Ukelson

10:00-10:30 Multiple Alignment of Biological Networks: A Flexible Approach
Yves-Pol Denielou, Frédéric Boyer, Marie-France Sagot and Alain Viari

10:30-11:00 Coffee break

Invited talk Chair: Esko Ukkonen

11:00-12:00 Graph mining: Patterns, Generators and Tools
Christos Faloutsos

Bioinformatics: Phylogenetic networks Chair: Esko Ukkonen

12:00-12:30 Level-k Phylogenetic Network can be Constructed from a Dense Triplet Set in Polynomial Time
Thu-Hien To and Michel Habib

12:30-13:00 The Structure of Level-k Phylogenetic Networks
Philippe Gambette, Vincent Berry and Christophe Paul

13:00-14:30 Lunch

Bioinformatics: Average-case analysis Chair: Rolf Backhofen

14:30-15:00 Finding All Sorting Tandem Duplication Random Loss Operations
Matthias Bernt, Ming-Chiang Chen, Daniel Merkle, Hung-Lung Wang, Kun-Mao Chao and Martin Middendorf

15:00-15:30 Average-case analysis of perfect sorting by reversals (extended abstract)
Mathilde Bouvel, Cedric Chauve, Marni Mishna and Dominique Rossin

15:30-16:00 Statistical properties of factor oracles
Jeremie Bourdon and Irena Rusu

16:00-16:30 Coffee break

Bioinformatics: Haplotype inference Chair: Thierry Lecroq

16:30-17:00 Haplotype Inference Constrained by Plausible Haplotype Data
Michael Fellows, Tzvika Hartman, Danny Hermelin, Gad Landau, Frances A. Rosamond and Liat Rozenberg

17:00-17:30 Efficient Inference of Haplotypes from Genotypes on a Pedigree with Mutations and Missing Alleles
Wei-Bung Wang and Tao Jiang

program.txt · Last modified: 2009/06/17 08:54