Approximating tree edit distance through string edit distance

DOI10.1007/S00453-008-9213-ZMaRDI QIDQ2379923zbMATH OpenOpenAlexFDO

Authors Tatsuya Akutsu, Daiji Fukagawa, Atsuhiro Takasu

Publication date 23 March 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-008-9213-z

zbMATH Keywords

embeddingapproximation algorithmsstring matchingtree edit distanceEuler string

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• Approximating Tree Edit Distance Through String Edit Distance
• A relation between edit distance for ordered trees and edit distance for Euler strings
• Approximating tree edit distance through string edit distance for binary tree codes
• Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes
• scientific article; zbMATH DE number 1305084

Cites work

• scientific article; zbMATH DE number 1615297 (Why is no real title available?)
• scientific article; zbMATH DE number 1305084 (Why is no real title available?)
• scientific article; zbMATH DE number 1820633 (Why is no real title available?)
• scientific article; zbMATH DE number 2119725 (Why is no real title available?)
• scientific article; zbMATH DE number 1445304 (Why is no real title available?)
• A relation between edit distance for ordered trees and edit distance for Euler strings
• A survey on tree edit distance and related problems
• An Optimal Decomposition Algorithm for Tree Edit Distance
• Approximate nearest neighbors and sequence comparison with block operations
• Improved lower bounds for embeddings into L₁
• Low distortion embeddings for edit distance
• New algorithm for ordered tree-to-tree correction problem
• Nonembeddability theorems via Fourier analysis
• Oblivious string embeddings and edit distance approximations
• On finding common subtrees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• The Tree-to-Tree Correction Problem

Cited in

(7)

• Edit distance between unrooted trees in cubic time
• A relation between edit distance for ordered trees and edit distance for Euler strings
• Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes
• Fast similarity search for graphs by edit distance
• Approximating tree edit distance through string edit distance for binary tree codes
• Classes of cost functions for string edit distance
• Approximating Tree Edit Distance Through String Edit Distance

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 Q2379923)