CPM 2015

26th Annual Symposium on Combinatorial Pattern Matching

Ischia Island, Italy, June 29-July 1, 2015


Papers and Proceedings

Local information



Accepted Papers

Djamal Belazzougui, Fabio Cunial, Travis Gagie, Nicola Prezza and Mathieu Raffinot. Composite repetition-aware data structures
Pooya Davoodi, John Iacono, Gad M. Landau and Moshe Lewenstein. Range Minimum Query Indexes in Higher Dimensions
Amihood Amir and Benny Porat. On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling
Pawel Gawrychowski and Patrick K. Nicholson. Encodings of Range Maximum-Sum Segment Queries and Applications
Ron Zeira and Ron Shamir. Sorting by cuts, joins and duplications
Yoshiaki Matsuoka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda. Semi-dynamic compact index for short patterns and succinct van Emde Boas tree
Gabriel Istrate and Cosmin Bonchis. Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley's process
Johannes Fischer, Tomohiro I and Dominik Köppl. Lempel Ziv Computation In Small Space (LZ-CISS)
Sukhyeun Cho, Joong Chae Na and Jeong Seop Sim. Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem
Alexander Loptev, Gregory Kucherov and Tatiana Starikovskaya. On Maximal Unbordered Factors
Dmitry Kosolobov. Online Detection of Repetitions with Backtracking
Rayan Chikhi, Paul Medvedev, Martin Milanic and Sofya Raskhodnikova. On the readability of overlap digraphs
Sudip Biswas, Arnab Ganguly, Rahul Shah and Sharma Thankachan. Ranked Document Retrieval With Forbidden Pattern
Gonzalo Navarro and Sharma V. Thankachan. Reporting Closest Substring Occurrences Under Bounded Gap Constraints
Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Gad M. Landau and Oren Weimann. Longest Common Extensions in Trees
Djamal Belazzougui and Fabio Cunial. A framework for space-efficient string kernels
Jesper Jansson, Andrzej Lingas and Eva-Marta Lundell. The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets
Johannes Fischer and Pawel Gawrychowski. Alphabet-Dependent String Searching with Wexponential Search Trees
Ivan Bliznets, Fedor Fomin, Petr Golovach, Nikolay Karpov, Alexander Kulikov and Saket Saurabh. Parameterized Complexity of Superstring Problems
Timo Beller and Enno Ohlebusch. Efficient construction of a compressed de Bruijn graph for pan-genome analysis
Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen, Moshe Lewenstein and Hjalte Wedel Vildhøj. Longest Common Extensions in Sublinear Space
Cyril Nicaud. A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm
Jozef Hales, Jan Manuch, Yann Ponty and Ladislav Stacho. Combinatorial RNA Design: Designability and Structure-Approximating Algorithm
Juha Kärkkäinen, Dominik Kempa and Simon Puglisi. Parallel External Memory Suffix Sorting
Keisuke Goto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda. LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding
Simon Gog and Matthias Petri. Compact Indexes for Flexible Top-k Retrieval
Juha Kärkkäinen, Dominik Kempa and Marcin Piątkowski. Tighter Bounds for the Sum of Irreducible LCP Values
Timothy M. Chan and Moshe Lewenstein. Fast String Dictionary Lookup with One Error
Arnab Ganguly, Sharma V. Thankachan and Rahul Shah. Succinct Non-overlapping Indexing
Wing-Kai Hon, Tak-Wah Lam, Rahul Shah, Sharma V. Thankachan, Hing-Fung Ting and Yilin Yang. Dictionary Matching With Uneven Gaps
Patrick K. Nicholson and Rajeev Raman. Encoding Nearest Larger Values
Paola Bonizzoni, Riccardo Dondi, Gunnar W. Klau, Yuri Pirola, Nadia Pisanti and Simone Zaccaria. On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction problem
Alexander Kulikov, Sergey Savinov and Evgeniy Sluzhaev. Greedy Conjecture for Strings of Length 4