DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2022.115

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

Authors: Masoud Seddighin and Saeed Seddighin

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

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.

Cite as

Masoud Seddighin and Saeed Seddighin. 3+ε Approximation of Tree Edit Distance in Truly Subquadratic Time. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 115:1-115:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ITCS.2022.115},
  URN =		{urn:nbn:de:0030-drops-157116},
  doi =		{10.4230/LIPIcs.ITCS.2022.115},
  annote =	{Keywords: tree edit distance, approximation, subquadratic, edit distance}
}

Search Results

Documents authored by Seddighin, Masoud

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

Abstract

Cite as

Thanks for your feedback!

Could not send message