Binary jumbled pattern matching on trees and tree-like structures

DOI10.1007/S00453-014-9957-6zbMATH1330.68358OpenAlexW2124531545MaRDI QIDQ893318FDOQ893318

Authors Travis Gagie, Danny Hermelin, Gad M. Landau, Oren Weimann

Publication date 19 November 2015

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.6127

zbMATH Keywords

pattern matchinggrammar compressionpermutation pattern matchingtree pattern matchinggraph motifs

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Abstract: Binary jumbled pattern matching asks to preprocess a binary string $S$ in order to answer queries $(i,j)$ which ask for a substring of $S$ that is of length $i$ and has exactly $j$ 1-bits. This problem naturally generalizes to vertex-labeled trees and graphs by replacing "substring" with "connected subgraph". In this paper, we give an $O(n^2/lo{g}^{2}n)$-time solution for trees, matching the currently best bound for (the simpler problem of) strings. We also give an $Oh{g}^{2/3}{n}^{4/3}/(logn{)}^{4/3}$-time solution for strings that are compressed by a grammar of size $g$. This solution improves the known bounds when the string is compressible under many popular compression schemes. Finally, we prove that the problem is fixed-parameter tractable with respect to the treewidth $w$ of the graph, thus improving the previous best $n^{O(w)}$ algorithm [ICALP'07].

Recommendations

• Binary jumbled pattern matching on trees and tree-like structures
• Binary jumbled string matching for highly run-length compressible texts
• New algorithms for binary jumbled pattern matching
• Algorithms for jumbled pattern matching in strings
• Fast and simple jumbled indexing for binary run-length encoded strings

Cites work

• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithms for jumbled pattern matching in strings
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Binary jumbled string matching for highly run-length compressible texts
• Complexity issues in vertex-colored graph pattern matching
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Finding approximate and constrained motifs in graphs
• Indexing permutations for binary strings
• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• New algorithms for binary jumbled pattern matching
• On approximate jumbled pattern matching in strings
• On hardness of jumbled indexing
• On the Kernelization Complexity of Colorful Motifs
• Optimal on-line decremental connectivity in trees
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• The Smallest Grammar Problem
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Variations on the Common Subexpression Problem

Cited in

(11)

• Segmenting Strings Homogeneously Via Trees
• Reconstruction of trees from jumbled and weighted subtrees
• scientific article; zbMATH DE number 7286689 (Why is no real title available?)
• A new linear-time algorithm for centroid decomposition
• Bubble-flip -- a new generation algorithm for prefix normal words
• Jump interpolation search trees and symmetric binary numbers
• Binary jumbled pattern matching on trees and tree-like structures
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• On infinite prefix normal words
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word

This page was built for publication: Binary jumbled pattern matching on trees and tree-like structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q893318)