A relation between edit distance for ordered trees and edit distance for Euler strings

DOI10.1016/j.ipl.2006.06.002zbMath1185.68829MaRDI QIDQ845840

Tatsuya Akutsu

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.06.002

zbMATH Keywords

algorithms; alignment; ordered trees; edit distance; Euler string

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

Related Items

Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes, Which XML schemas are streaming bounded repairable?, A bisection algorithm for grammar-based compression of ordered trees, A metric for rooted trees with unlabeled vertices based on nested parentheses, Approximate joins for XML at label level, Approximating tree edit distance through string edit distance, Sublinear DTD Validity

Cites Work

• Unnamed Item
• A survey on tree edit distance and related problems
• New Algorithm for Ordered Tree-to-Tree Correction Problem
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• The Tree-to-Tree Correction Problem
• Fast algorithms for the unit cost editing distance between trees
• Low distortion embeddings for edit distance