Combinatorial Pattern Matching (eBook)

On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling.- A Framework for Space-Efficient String Kernels.- Composite Repetition-Aware Data Structures.- Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis.- Longest Common Extensions in Trees.- Longest Common Extensions in Sublinear Space.- Ranked Document Retrieval with Forbidden Pattern.- Parameterized Complexity of Superstring Problems.- On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem.- Fast String Dictionary Lookup with One Error.- On the Readability of Overlap Digraphs.- Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem.- Range Minimum Query Indexes in Higher Dimensions.-
Alphabet-Dependent String Searching with Wexponential Search Trees.- Lempel Ziv Computation in Small Space (LZ-CISS).- Succinct Non-overlapping Indexing.- Encodings of Range Maximum-Sum Segment Queries and Applications.- Compact Indexes for Flexible Top-k Retrieval.- LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding.- Combinatorial RNA Design: Designability and Structure-Approximating Algorithm.- Dictionary Matching with Uneven Gaps.- Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley’s Process.- The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets.- String Powers in Trees.- Online Detection of Repetitions with Backtracking.- Greedy Conjecture for Strings of Length 4.- Tighter Bounds for the Sum of Irreducible LCP Values.- Parallel External Memory Suffix Sorting.- On Maximal Unbordered Factors.- Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree.- Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints.- A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS
Algorithm.- Encoding Nearest Larger Values.- Sorting by Cuts, Joins and Whole Chromosome Duplications.