Combinatorial Pattern Matching : 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings / edited by Ferdinando Cicalese, Ely Porat, Ugo Vaccaro.

Format:

Book

Contributor:

Cicalese, Ferdinando, editor.

Porat, Ely, editor.

Vaccaro, Ugo, editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

LNCS sublibrary. Theoretical computer science and general issues ; SL 1, 9133.

Theoretical Computer Science and General Issues ; 9133

Language:

English

Subjects (All):

Pattern perception.

Algorithms.

Numerical analysis.

Computer science--Mathematics.

Computer science.

Data structures (Computer science).

Bioinformatics.

Pattern Recognition.

Algorithm Analysis and Problem Complexity.

Numeric Computing.

Discrete Mathematics in Computer Science.

Data Structures.

Computational Biology/Bioinformatics.

Local Subjects:

Pattern Recognition.

Algorithm Analysis and Problem Complexity.

Numeric Computing.

Discrete Mathematics in Computer Science.

Data Structures.

Computational Biology/Bioinformatics.

Physical Description:

1 online resource (XIX, 412 pages) : 69 illustrations.

Edition:

First edition 2015.

Contained In:

Springer eBooks

Place of Publication:

Cham : Springer International Publishing : Imprint: Springer, 2015.

System Details:

text file PDF

Summary:

This book constitutes the refereed proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015, held on Ischia Island, Italy, in June/July 2015. The 34 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 83 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 combinatorial properties of such structures and to exploit these properties in order to achieve superior performance for the corresponding computational problems. The meeting also deals with problems in computational biology; data compression and data mining; coding; information retrieval; natural language processing; and pattern recognition.

Contents:

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.

Other Format:

Printed edition:

ISBN:

978-3-319-19929-0

9783319199290

Access Restriction:

Restricted for use by site license.