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

DOI10.1016/J.JDA.2011.12.018zbMATH Open1248.68170OpenAlexW2291432131WikidataQ59278876 ScholiaQ59278876MaRDI QIDQ450558FDOQ450558

Authors Yusaku Kaneta, Hiroki Arimura, 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)

Recommendations

• Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism
• Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees
• Ordered and Unordered Tree Inclusion
• Tree template matching in unranked ordered trees
• Constrained tree inclusion

Cites Work

• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1754502 (Why is no real title available?)
• A Four Russians algorithm for regular expression pattern matching
• A survey on tree edit distance and related problems
• Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees
• Conjunctive queries over trees
• Constrained tree inclusion
• Functions realizable with word-parallel logical and two's-complement addition instructions
• More Efficient Algorithm for Ordered Tree Inclusion
• New Algorithms for Regular Expression Matching
• Ordered and Unordered Tree Inclusion
• Pattern Matching in Trees
• Sorting in linear time?
• The art of computer programming. Vol. 4, Fasc. 0--4. Fasc. 0: Introduction to combinatorial algorithms and Boolean functions. Fasc. 1: Bitwise tricks \& techniques, binary decision diagrams. Fasc. 2: Generating all tuples and permutations. Fasc. 3: Generating all combinations and partitions. Fasc. 4: Generating all trees. History of combinatorial generation.
• The tree inclusion problem

Cited In (3)

• Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees
• Fast parallel reordering and isomorphism testing of \(k\)-trees
• Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism

Uses Software

• XPath

This page was built for publication: Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism

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