Approximating Tree Edit Distance Through String Edit Distance

DOI10.1007/11940128_11MaRDI QIDQ5459105zbMATH OpenOpenAlexFDO

Authors Tatsuya Akutsu, Daiji Fukagawa, Atsuhiro Takasu

Publication date 24 April 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11940128_11

Mathematics Subject Classification ID

Approximation algorithms (68W25) Protein sequences, DNA sequences (92D20)

Recommendations

• Approximating tree edit distance through string edit distance
• \(1+\varepsilon\) approximation of tree edit distance in quadratic time
• Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes
• Approximating tree edit distance through string edit distance for binary tree codes
• A relation between edit distance for ordered trees and edit distance for Euler strings

Cited in

(9)

• Classes of cost functions for string edit distance
• Approximating tree edit distance through string edit distance
• scientific article; zbMATH DE number 1844616 (Why is no real title available?)
• Approximate joins for XML at label level
• \(1+\varepsilon\) approximation of tree edit distance in quadratic time
• Approximating tree edit distance through string edit distance for binary tree codes
• Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes
• On the hardness of computing the edit distance of shallow trees
• A relation between edit distance for ordered trees and edit distance for Euler strings

This page was built for publication: Approximating Tree Edit Distance Through String Edit Distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5459105)