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

fine-grained complexitySETHsubtree isomorphism

Mathematics Subject Classification ID

Trees (05C05) 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) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

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

(15)

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

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)