# Reduction from OV to Largest Common Subtree

Revision as of 12:19, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: OV TO: Largest Common Subtree == Description == == Implications == assume: OVH<br/>then: for all constants $d \geq {2}$, target on two rooted trees of size at most $n$, degree $d$, and height $h \leq \log_d n + O(\log \log n)$ cannot be solved in truly subquadtratic $O(n^{2-\epsilon})$ time == Year == 2018 == Reference == Abboud, A., Backurs, A., Hansen, T. D., Vassilevska Williams, V., & Zamir, O. (2018). Subtree isomorphism revisited. ACM Tra...")

FROM: OV TO: Largest Common Subtree

## Description

## Implications

assume: OVH

then: for all constants $d \geq {2}$, target on two rooted trees of size at most $n$, degree $d$, and height $h \leq \log_d n + O(\log \log n)$ cannot be solved in truly subquadtratic $O(n^{2-\epsilon})$ time

## Year

2018

## Reference

Abboud, A., Backurs, A., Hansen, T. D., Vassilevska Williams, V., & Zamir, O. (2018). Subtree isomorphism revisited. ACM Transactions on Algorithms (TALG), 14(3), 1-23.