When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.115
URN: urn:nbn:de:0030-drops-157116
URL: https://drops.dagstuhl.de/opus/volltexte/2022/15711/
 Go to the corresponding LIPIcs Volume Portal

### 3+ε Approximation of Tree Edit Distance in Truly Subquadratic Time

 pdf-format:

### Abstract

Tree edit distance is a well-known generalization of the edit distance problem to rooted trees. In this problem, the goal is to transform a rooted tree into another rooted tree via (i) node addition, (ii) node deletion, and (iii) node relabel. In this work, we give a truly subquadratic time algorithm that approximates tree edit distance within a factor 3+ε.
Our result is obtained through a novel extension of a 3-step framework that approximates edit distance in truly subquadratic time. This framework has also been previously used to approximate longest common subsequence in subquadratic time.

### BibTeX - Entry

@InProceedings{seddighin_et_al:LIPIcs.ITCS.2022.115,
author =	{Seddighin, Masoud and Seddighin, Saeed},
title =	{{3+\epsilon Approximation of Tree Edit Distance in Truly Subquadratic Time}},
booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages =	{115:1--115:22},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-217-4},
ISSN =	{1868-8969},
year =	{2022},
volume =	{215},
editor =	{Braverman, Mark},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
}