Binary jumbled pattern matching on trees and tree-like structures
type: Item
instance of: scholarly article
title: Binary jumbled pattern matching on trees and tree-like structures
zbMATH Open document ID: 1330.68358
author: Travis Gagie
author: Danny Hermelin
author: Gad M. Landau
author: Oren Weimann
published in: Algorithmica
publication date: 2015-11-19T00:00:00Z
full work available at URL: https://arxiv.org/abs/1301.6127
Mathematics Subject Classification ID: 68W32
zbMATH DE Number: 6511727
zbMATH Keywords: pattern matching
zbMATH Keywords: tree pattern matching
zbMATH Keywords: permutation pattern matching
zbMATH Keywords: grammar compression
zbMATH Keywords: graph motifs
MaRDI profile type: Publication
OpenAlex ID: W2124531545
arXiv ID: 1301.6127
cites work: Optimal on-line decremental connectivity in trees
cites work: On the Kernelization Complexity of Colorful Motifs
cites work: On Hardness of Jumbled Indexing
cites work: Binary jumbled string matching for highly run-length compressible texts
cites work: Indexing permutations for binary strings
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Q4699283
cites work: Upper and lower bounds for finding connected motifs in vertex-colored graphs
cites work: Algorithms for jumbled pattern matching in strings
cites work: On approximate jumbled pattern matching in strings
cites work: The Smallest Grammar Problem
cites work: Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
cites work: Complexity issues in vertex-colored graph pattern matching
cites work: Finding Approximate and Constrained Motifs in Graphs
cites work: Variations on the Common Subexpression Problem
cites work: New algorithms for binary jumbled pattern matching
cites work: Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet
cites work: Sub-quadratic time and linear space data structures for permutation matching in binary strings
cites work: Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
DOI: 10.1007/S00453-014-9957-6
description: scientific article