Binary jumbled pattern matching on trees and tree-like structures

DOI10.1007/S00453-014-9957-6zbMATH Open1330.68358arXiv1301.6127OpenAlexW2124531545MaRDI QIDQ893318FDOQ893318

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

Publication date: 19 November 2015

Published in: Algorithmica (Search for Journal in Brave)

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].

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

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

zbMATH Keywords

pattern matchinggrammar compressionpermutation pattern matchingtree pattern matchinggraph motifs

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Finding approximate and constrained motifs in graphs
• Title not available (Why is that?)
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Variations on the Common Subexpression Problem
• Optimal on-line decremental connectivity in trees
• 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
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• On Hardness of Jumbled Indexing
• On approximate jumbled pattern matching in strings
• On the Kernelization Complexity of Colorful Motifs
• Complexity issues in vertex-colored graph pattern matching
• Binary jumbled string matching for highly run-length compressible texts
• Indexing permutations for binary strings
• The Smallest Grammar Problem
• New algorithms for binary jumbled pattern matching

Cited In (9)

• Bubble-flip -- a new generation algorithm for prefix normal words
• Jump interpolation search trees and symmetric binary numbers
• Title not available (Why is that?)
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• On infinite prefix normal words
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Segmenting Strings Homogeneously Via Trees
• A new linear-time algorithm for centroid decomposition
• Efficient indexes for jumbled pattern matching with constant-sized alphabet

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)