| Description |
1 online resource |
| Series |
Lecture notes in computer science, 0302-9743 ; 7354 |
|
LNCS Sublibrary. Sl 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 7354.
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
Gene Regulation, Protein Networks and Disease: A Computational Perspective / Ron Shamir -- Wavelet Trees for All / Gonzalo Navarro -- The Maximum Number of Squares in a Tree / Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica and Jakub Radoszewski, et al. -- Faster and Simpler Minimal Conflicting Set Identification / (Extended Abstract) / Aïda Ouangraoua and Mathieu Raffinot -- Partitioning into Colorful Components by Minimum Edge Deletions / Sharon Bruckner, Falk Hüffner, Christian Komusiewicz, Rolf Niedermeier and Sven Thiel, et al. -- Approximation Algorithms and Hardness Results for Shortest Path Based Graph Orientations / Dima Blokh, Danny Segev and Roded Sharan -- Constant-Time Word-Size String Matching / Dany Breslauer, Leszek Gąsieniec and Roberto Grossi -- Pattern Matching in Multiple Streams / Raphaël Clifford, Markus Jalsenius, Ely Porat and Benjamin Sach -- An Efficient Linear Pseudo-minimization Algorithm for Aho-Corasick Automata / Omar AitMous, Frédérique Bassino and Cyril Nicaud -- Efficient Two-Dimensional Pattern Matching with Scaling and Rotation and Higher-Order Interpolation / Christian Hundt and Florian Wendland -- Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths / Guillaume Blin, Laurent Bulteau, Minghui Jiang, Pedro J. Tejada and Stéphane Vialette -- Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence / Ferdinando Cicalese, Eduardo Laber, Oren Weimann and Raphael Yuster -- The Complexity of String Partitioning / Anne Condon, Ján Maňuch and Chris Thachuk -- Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval / Wing-Kai Hon, Rahul Shah and Sharma V. Thankachan -- Document Listing for Queries with Excluded Pattern / Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan and Jeffrey Scott Vitter -- Cross-Document Pattern Matching / Gregory Kucherov, Yakov Nekrich and Tatiana Starikovskaya -- FEMTO: Fast Search of Large Sequence Collections / Michael P. Ferguson -- Speeding Up q-Gram Mining on Grammar-Based Compressed Texts / Keisuke Goto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda -- Simple and Efficient LZW-Compressed Multiple Pattern Matching / Paweł Gawrychowski -- Computing the Burrows-Wheeler Transform of a String and Its Reverse / Enno Ohlebusch, Timo Beller and Mohamed I. Abouelhoda -- Efficient Algorithm for Circular Burrows-Wheeler Transform / Wing-Kai Hon, Tsung-Han Ku, Chen-Hua Lu, Rahul Shah and Sharma V. Thankachan -- Least Random Suffix/Prefix Matches in Output-Sensitive Time / Niko Välimäki -- Compressed String Dictionary Look-Up with Edit Distance One / Djamal Belazzougui and Rossano Venturini -- Time-Space Trade-Offs for Longest Common Extensions / Philip Bille, Inge Li Gørtz, Benjamin Sach and Hjalte Wedel Vildhøj -- Local Exact Pattern Matching for Non-fixed RNA Structures / Mika Amit, Rolf Backofen, Steffen Heyne, Gad M. Landau and Mathias Möhl, et al. -- Impact of the Energy Model on the Complexity of RNA Folding with Pseudoknots / Saad Sheikh, Rolf Backofen and Yann Ponty -- Finding Longest Common Segments in Protein Structures in Nearly Linear Time / Yen Kaow Ng, Hirotaka Ono, Ling Ge and Shuai Cheng Li -- A Linear Kernel for the Complementary Maximal Strip Recovery Problem / Haitao Jiang and Binhai Zhu -- Efficient Exponential Time Algorithms for Edit Distance between Unordered Trees / Tatsuya Akutsu, Takeyuki Tamura, Daiji Fukagawa and Atsuhiro Takasu -- Fixed-Parameter Algorithms for Finding Agreement Supertrees / David Fernández-Baca, Sylvain Guillemot, Brad Shutters and Sudheer Vakati -- Computing the Rooted Triplet Distance between Galled Trees by Counting Triangles / Jesper Jansson and Andrzej Lingas -- Minimum Leaf Removal for Reconciliation: Complexity and Algorithms / Riccardo Dondi and Nadia El-Mabrouk -- On the Closest String via Rank Distance / Liviu P. Dinu and Alexandru Popa -- On Approximating String Selection Problems with Outliers / Christina Boucher, Gad M. Landau, Avivit Levy, David Pritchard and Oren Weimann -- The Parameterized Complexity of the Shared Center Problem / Zhi-Zhong Chen, Lusheng Wang and Wenji Ma |
| Summary |
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 |
| Analysis |
Computer science |
|
Data structures (Computer science) |
|
Computer software |
|
Electronic data processing |
|
Computational complexity |
|
Optical pattern recognition |
|
Bioinformatics |
|
Pattern Recognition |
|
Algorithm Analysis and Problem Complexity |
|
Numeric Computing |
|
Discrete Mathematics in Computer Science |
|
Data Structures |
|
Computational Biology/Bioinformatics |
| Bibliography |
Includes bibliographical references and author index |
| Subject |
Computer algorithms -- Congresses
|
|
Combinatorial analysis -- Congresses
|
|
Informatique.
|
|
Combinatorial analysis
|
|
Computer algorithms
|
| Genre/Form |
Conference papers and proceedings
|
|
Software.
|
| Form |
Electronic book
|
| Author |
Kärkkäinen, Juha
|
|
Stoye, Jens.
|
| ISBN |
9783642312656 |
|
3642312659 |
|
