Preliminary Program

Download the program in pdf.

Sunday, June 26th
17.00-19.30: Registration.
19.30-20.30: Welcome Aperitivo, Terrace of Hotel La Torre.

Monday, June 27th
8:15-8:45: Registration.
8:45-9:00: Opening.

Invited Talk (Chair Giovanni Manzini)
09.00-10.00: Gad Landau: Algorithms on Grammar-Compressed Strings.

CPM and Compressed Text I (Chair Juha Kärkkäinen)
10.00-10.20: Enno Ohlebusch and Simon Gog. Lempel-Ziv Factorization Revisited.
10.20-10.40: Chris Thachuk. Succincter Text Indexing with Wildcards.
10.40-11.00: Sebastian Kreft and Gonzalo Navarro. Self-Indexing Based on LZ77.
11.00-11-30: Coffee break

Combinatorics on Words  (Chair Aldo de Luca)
11.30-11.50: Haitao Jiang, Farong Zhong and Binhai Zhu. Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies.
11.50-12.10: David E. Daykin, Jacqueline W. Daykin and William F. Smyth. String Comparison & Lyndon-Like Factorization Using V-Order in Linear Time.
12.10-12.30: Antoine Deza, Frantisek Franek and Mei Jiang. A d-step approach for distinct squares in strings.
12.30-12.50: Cedric Chauve, Ján Maňuch, Murray Patterson and Roland Wittler. Tractability results for the Consecutive-Ones Property with multiplicity.
13.00: Lunch

CPM and Computational Biology I (Chair Michal Ziv-Ukelson)
15.00-15.20: Stefanie Schirmer and Robert Giegerich. Forest alignment with affine gaps and anchors.
15.20-15.40: Wolfgang Otto, Peter F. Stadler and Sonja J. Prohaska. Phylogenetic Footprinting and Consistent Sets of Local Alignments.
15.40-16.00: Michel Habib and  Juraj Stacho. Unique perfect phylogeny is NP-hard.
16.00-16.20: Daniel G. Brown and Jakub Truszkowski. Fast error-tolerant quartet phylogeny algorithms.
16.20-16.50: Coffee break

Classic String Matching I (Chair Sabrina Mantaci)
16.50-17.10: Dany Breslauer and Zvi Galil. Real-Time Streaming String Matching.
17.10-17.30: Dany Breslauer, Roberto Grossi and Filippo Mignosi. Simple Real-Time Constant-Space String-Matching.
17.30-17.50: Raphäel Clifford, Markus Jalsenius, Ely Porat and Benjamin Sach. Space Lower Bounds for On-line Pattern Matching.
18.00-19.00: Business Meeting and Best Student Paper Award Ceremony.

Tuesday, June 28th
Invited Talk (Chair Raffaele Giancarlo)
09.00-10.00: Nello Cristianini: Automatic Discovery of Patterns in Media Content.

CPM and Compressed Text II (Chair Gonzalo Navarro)
10.00-10.20: Travis Gagie and Juha Kärkkäinen. Counting Colours in Compressed Strings.
10.20-10.40: German Tischler. On Wavelet Tree Construction.
10.40-11.00: Markus J. Bauer, Anthony J. Cox and Giovanna Rosone. Lightweight BWT Construction for Very Large String Collections.
11.00-11-30: Coffee break.

Classic String Matching II (Chair Chiara Epifanio)
11.30-11.50: Tomohiro I, Shunsuke Inenaga and Masayuki Takeda. Palindrome Pattern Matching.
11.50-12.10: Takashi Uemura and Hiroki Arimura. Sparse and Truncated Suffix Trees on Variable-Length Codes.
12.10-12.30: Paolo Ferragina. On the Weak Prefix-Search problem.
12.30-12.50: Isaac B. Goldstein and Moshe Lewenstein. Quick Greedy Computation for Minimum Common String Partitions.

13.00: Lunch.
15.30: Social Tour.
20.00: Social Dinner at Grand Hotel Piazza Borsa, Palermo.

Wednesday, June 29th
Invited Talk (Chair Maxime Crochemore)
09.00-10.00: Martin Vingron: Computational Regulatory Genomics.

CPM and Compressed Text III (Chair Travis Gagie)
10.00-10.20: Jérémy Barbay, Johannes Fischer and Gonzalo Navarro. LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations.
10.20-10.40: Philip Bille and Inge Li Gørtz. Substring Range Reporting.
10.40-11.00: Takanori Yamamoto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda. Faster Subsequence and Don’t-Care Pattern Matching on Compressed Texts.
11.00-11-30: Coffee break.

CPM and Computational Biology II (Chair Max Alekseyev)
11.30-11.50: Yassin Refahi, Etienne Farcot, Yann Guédon, Fabrice Besnard, Teva Vernoux and Christophe Godin. A Combinatorial Model of Phyllotaxis Perturbations in Arabidopsis thaliana.
11.50-12.10: Laurent Bulteau, Guillaume Fertin, Minghui Jiang and Irena Rusu. Tractability and Approximability of Maximal Strip Recovery.
12.10-12.30: Michalis Christou, Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Bartosz Szreder and Tomasz Walen. Efficient Seeds Computation Revisited.
12.30-12.50: Domenico Cantone, Salvatore Cristofaro and Simone Faro. Efficient Matching of Biological Sequences Allowing for Non-Overlapping Inversions.
13.00-15.00: Lunch.

Trees and Graphs (Chair Giosuè Lo Bosco)
15.00-15.20: Jesper Nielsen. A Coarse-to-Fine Approach to Computing the k-best Viterbi Paths.
15.20-15.40: Riccardo Dondi, Guillaume Fertin and Stéphane Vialette. Finding Approximate and Constrained Motifs in Graphs.
15.40-16.00: Kouichi Hirata, Yoshiaki Yamaoto and Tetsuji Kuboyama. Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees.
16.00-16.20: Michael Elberfeld, Danny Segev, Colin R. Davidson, Dana Silverbush and Roded Sharan. Approximation Algorithms for Orienting Mixed Graphs.
16.20-16.50: Coffee break.

Classic String Matching III (Chair Gregory Kucherov)
16.50-17.10: Stéphane Gosselin, Guillaume Damiand and Christine Solnon. Frequent Submap Discovery.
17.10-17.30: Tamar Pinhas, Dekel Tsur, Shay Zakov and Michal Ziv-Ukelson. Edit Distance with Duplications and Contractions Revisited.
17.30-17.50: Marek Cygan, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter and Tomasz Walen. Polynomial-Time Approximation Algorithms for Weighted LCS Problem.
17.50-18.10: Raphäel Clifford, Zvi Gotthilf, Moshe Lewenstein and Alexandru Popa. Restricted Common Superstring and Restricted Common Supersequence.