Binary jumbled pattern matching on trees and tree-like structures
From MaRDI portal
Publication:893318
DOI10.1007/s00453-014-9957-6zbMath1330.68358arXiv1301.6127MaRDI QIDQ893318
Travis Gagie, Danny Hermelin, Oren Weimann, Gad M. Landau
Publication date: 19 November 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1301.6127
68W32: Algorithms on strings
Related Items
Unnamed Item, On infinite prefix normal words, Bubble-flip -- a new generation algorithm for prefix normal words, Fast algorithms for abelian periods in words and greatest common divisor queries, Efficient indexes for jumbled pattern matching with constant-sized alphabet, Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
Cites Work
- Unnamed Item
- Optimal on-line decremental connectivity in trees
- Indexing permutations for binary strings
- Sub-quadratic time and linear space data structures for permutation matching in binary strings
- Complexity issues in vertex-colored graph pattern matching
- On approximate jumbled pattern matching in strings
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- New algorithms for binary jumbled pattern matching
- Binary jumbled string matching for highly run-length compressible texts
- Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet
- Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
- ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
- Finding Approximate and Constrained Motifs in Graphs
- On the Kernelization Complexity of Colorful Motifs
- The Smallest Grammar Problem
- Variations on the Common Subexpression Problem
- On Hardness of Jumbled Indexing
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
