Subtree isomorphism revisited

DOI10.1145/3093239MaRDI QIDQ4554355zbMATH OpenOpenAlexWikidataFDO

Authors Amir Abboud, Artūrs Bačkurs, Thomas Dueholm Hansen, Or Zamir, Virginia Vassilevska Williams

Publication date 13 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3093239

zbMATH Keywords

subtree isomorphismSETHfine-grained complexity

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Subtree isomorphism revisited
• Faster Subtree Isomorphism
• Strings, trees, and patterns
• Faster algorithms for the maximum common subtree isomorphism problem
• A note on the subtree isomorphism for ordered trees and related problems

Cited in

(12)

• Some comments on the subtree isomorphism problem for ordered trees
• Isomorphism Types of Trees
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Subtree isomorphism is in random NC
• Strings, trees, and patterns
• Subtree isomorphism revisited
• Dichotomies for tree minor containment with structural parameters
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• Dichotomies for tree minor containment with structural parameters
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• scientific article; zbMATH DE number 871916 (Why is no real title available?)
• The complexity of approximate pattern matching on de Bruijn graphs

This page was built for publication: Subtree isomorphism revisited

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