A survey on tree edit distance and related problems
type: Item
instance of: scholarly article
title: A survey on tree edit distance and related problems
zbMATH Open document ID: 1078.68152
author: Philip Bille
published in: Theoretical Computer Science
publication date: 2005-06-30T00:00:00Z
review text: The paper deals with matching problems based on simple primitive operations applied to labeled trees. Particularly, tree edit distance problem, tree alignment distance problem and tree inclusion problem are surveyed. In order to do that, problems and algorithms are presented in a common framework. For each problem and its variations both ordered and unordered versions are reviewed. Also central algorithms for each of the poblems are presented in more detail, including proof of correctness and time complexity analysis. The paper concludes with a summary of results in table form and a short list of possible topics for further research.
reviewed by: Jozef Vyskoč
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 92D20
zbMATH DE Number: 2184054
zbMATH Keywords: tree matching problems
zbMATH Keywords: tree edit distance
zbMATH Keywords: tree alignment
zbMATH Keywords: tree inclusion
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.12.030
OpenAlex ID: W1978478796
cites work: Bounds on the Complexity of the Longest Common Subsequence Problem
cites work: Q4525728
cites work: Q4260368
cites work: Q4230322
cites work: More Efficient Algorithm for Ordered Tree Inclusion
cites work: New algorithm for ordered tree-to-tree correction problem
cites work: Introduction to algorithms
cites work: Q3128909
cites work: Q4198056
cites work: Finding largest subtrees and smallest supertrees
cites work: Algorithms on Strings, Trees and Sequences
cites work: Fast Algorithms for Finding Nearest Common Ancestors
cites work: Pattern Matching in Trees
cites work: Q4547753
cites work: Alignment of trees -- an alternative to tree edit
cites work: Ordered and Unordered Tree Inclusion
cites work: Q4952689
cites work: Q4252025
cites work: Q5585021
cites work: Fast parallel and serial approximate string matching
cites work: A Tree-to-Tree Distance and Its Application to Cluster Analysis
cites work: A Tree-Matching Algorithm Based on Node Splitting and Merging
cites work: Q4551373
cites work: On the complexity of finding iso- and other morphisms for partial \(k\)- trees
cites work: FINDING SMALLEST SUPERTREES UNDER MINOR CONTAINMENT
cites work: Nonlinear pattern matching in trees
cites work: The tree-to-tree editing problem
cites work: Fast algorithms for the unit cost editing distance between trees
cites work: The Tree-to-Tree Correction Problem
cites work: Finding approximate patterns in strings
cites work: The String-to-String Correction Problem
cites work: A constrained edit distance between unordered labeled trees
cites work: Some MAX SNP-hard results concerning unordered labeled trees
cites work: Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
cites work: Approximate Tree Matching in the Presence of Variable Length Don′t Cares
cites work: On the editing distance between unordered labeled trees
DOI: 10.1016/J.TCS.2004.12.030
description: scientific article; zbMATH DE number 2184054