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

This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finland, in July 2012.
The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problems or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.

---

This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finalnd, in July 2012.
The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problems or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.

---

This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finalnd, in July 2012.
The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problems or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.
Content:
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 -

---

This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finalnd, in July 2012.
The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problems or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.
Content:
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 -
....