Subtree Isomorphism Revisited

DOI10.1145/3093239zbMath1454.68084OpenAlexW2949518505WikidataQ129685254 ScholiaQ129685254MaRDI QIDQ4554355

Or Zamir, Thomas Dueholm Hansen, Amir Abboud, Artūrs Bačkurs, 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

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

Related Items (4)

The complexity of approximate pattern matching on de Bruijn graphs ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties

This page was built for publication: Subtree Isomorphism Revisited