Combinatorial Pattern Matching: 23rd Annual Symposium, CPM 2012, Helsinki, Finland, July 3-5, 2012. Proceedings

Front Matter....Pages -
Gene Regulation, Protein Networks and Disease: A Computational Perspective....Pages 1-1
Wavelet Trees for All....Pages 2-26
The Maximum Number of Squares in a Tree....Pages 27-40
Faster and Simpler Minimal Conflicting Set Identification....Pages 41-55
Partitioning into Colorful Components by Minimum Edge Deletions....Pages 56-69
Approximation Algorithms and Hardness Results for Shortest Path Based Graph Orientations....Pages 70-82
Constant-Time Word-Size String Matching....Pages 83-96
Pattern Matching in Multiple Streams....Pages 97-109
An Efficient Linear Pseudo-minimization Algorithm for Aho-Corasick Automata....Pages 110-123
Efficient Two-Dimensional Pattern Matching with Scaling and Rotation and Higher-Order Interpolation....Pages 124-137
Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths....Pages 138-148
Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence....Pages 149-158
The Complexity of String Partitioning....Pages 159-172
Towards an Optimal Space-and-Query-Time Index for Top- k Document Retrieval....Pages 173-184
Document Listing for Queries with Excluded Pattern....Pages 185-195
Cross-Document Pattern Matching....Pages 196-207
FEMTO: Fast Search of Large Sequence Collections....Pages 208-219
Speeding Up q -Gram Mining on Grammar-Based Compressed Texts....Pages 220-231
Simple and Efficient LZW-Compressed Multiple Pattern Matching....Pages 232-242
Computing the Burrows-Wheeler Transform of a String and Its Reverse....Pages 243-256
Efficient Algorithm for Circular Burrows-Wheeler Transform....Pages 257-268
Least Random Suffix/Prefix Matches in Output-Sensitive Time....Pages 269-279
Compressed String Dictionary Look-Up with Edit Distance One....Pages 280-292
Time-Space Trade-Offs for Longest Common Extensions....Pages 293-305
Local Exact Pattern Matching for Non-fixed RNA Structures....Pages 306-320
Impact of the Energy Model on the Complexity of RNA Folding with Pseudoknots....Pages 321-333
Finding Longest Common Segments in Protein Structures in Nearly Linear Time....Pages 334-348
A Linear Kernel for the Complementary Maximal Strip Recovery Problem....Pages 349-359
Efficient Exponential Time Algorithms for Edit Distance between Unordered Trees....Pages 360-372
Fixed-Parameter Algorithms for Finding Agreement Supertrees....Pages 373-384
Computing the Rooted Triplet Distance between Galled Trees by Counting Triangles....Pages 385-398
Minimum Leaf Removal for Reconciliation: Complexity and Algorithms....Pages 399-412
On the Closest String via Rank Distance....Pages 413-426
On Approximating String Selection Problems with Outliers....Pages 427-438
The Parameterized Complexity of the Shared Center Problem....Pages 439-452
Back Matter....Pages -