License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.115
URN: urn:nbn:de:0030-drops-157116
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15711/
Seddighin, Masoud ;
Seddighin, Saeed
3+ε Approximation of Tree Edit Distance in Truly Subquadratic Time
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},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15711},
URN = {urn:nbn:de:0030-drops-157116},
doi = {10.4230/LIPIcs.ITCS.2022.115},
annote = {Keywords: tree edit distance, approximation, subquadratic, edit distance}
}
|
Keywords: |
|
tree edit distance, approximation, subquadratic, edit distance |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
