Approximating tree edit distance through string edit distance

DOI10.1007/S00453-008-9213-ZzbMATH Open1184.68628OpenAlexW1966139659MaRDI QIDQ2379923FDOQ2379923

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

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

zbMATH Keywords

embeddingapproximation algorithmsstring matchingtree edit distanceEuler string

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites Work

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

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)