Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism

DOI10.1016/j.jda.2011.12.018zbMath1248.68170OpenAlexW2291432131WikidataQ59278876 ScholiaQ59278876MaRDI QIDQ450558

Hiroki Arimura, Yusaku Kaneta, Rajeev Raman

Publication date: 13 September 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.12.018

zbMATH Keywords

string matchingbit-parallel algorithmstree matchingunordered treesXML queries

Mathematics Subject Classification ID

Dynamic programming (90C39) Data structures (68P05)

Uses Software

• XPath

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey on tree edit distance and related problems
• Sorting in linear time?
• Constrained tree inclusion
• Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees
• The tree inclusion problem
• Conjunctive queries over trees
• New Algorithms for Regular Expression Matching
• Pattern Matching in Trees
• Functions realizable with word-parallel logical and two's-complement addition instructions
• A Four Russians algorithm for regular expression pattern matching
• More Efficient Algorithm for Ordered Tree Inclusion
• Ordered and Unordered Tree Inclusion