English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The edit distance between two rooted ordered trees with $n$ nodes labeledfrom an alphabet~$\Sigma$ is the minimum cost of transforming one tree into theother by a sequence of elementary operations consisting of deleting andrelabeling existing nodes, as well as inserting new nodes. Tree edit distanceis a well known generalization of string edit distance. The fastest knownalgorithm for tree edit distance runs in cubic $O(n^3)$ time and is based on asimilar dynamic programming solution as string edit distance. In this paper weshow that a truly subcubic $O(n^{3-\varepsilon})$ time algorithm for tree editdistance is unlikely: For $|\Sigma| = \Omega(n)$, a truly subcubic algorithmfor tree edit distance implies a truly subcubic algorithm for the all pairsshortest paths problem. For $|\Sigma| = O(1)$, a truly subcubic algorithm fortree edit distance implies an $O(n^{k-\varepsilon})$ algorithm for finding amaximum weight $k$-clique.  Thus, while in terms of upper bounds string edit distance and tree editdistance are highly related, in terms of lower bounds string edit distanceexhibits the hardness of the strong exponential time hypothesis [Backurs, IndykSTOC'15] whereas tree edit distance exhibits the hardness of all pairs shortestpaths. Our result provides a matching conditional lower bound for one of thelast remaining classic dynamic programming problems.

Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)