A Review on the Tree Edit Distance Problem and Related Path-Decomposition Algorithms

January 03, 2015 · The Cartographer · 🏛 arXiv.org

"No code URL or promise found in abstract"
"Title-pattern auto-detect: A Review on the Tree Edit Distance Problem and Related Path-Decomposition Algorithms"

Evidence collected by the PWNC Scanner

Authors Shihyen Chen arXiv ID 1501.00611 Category cs.DS: Data Structures & Algorithms Cross-listed cs.CC, cs.DM Citations 3 Venue arXiv.org Last Checked 4 days ago

Abstract

An ordered labeled tree is a tree in which the nodes are labeled and the left-to-right order among siblings is relevant. The edit distance between two ordered labeled trees is the minimum cost of changing one tree into the other through a sequence of edit steps. In the literature, there are a class of algorithms based on different yet closely related path-decomposition schemes. This article reviews the principles of these algorithms, and studies the concepts related to the algorithmic complexities as a consequence of the decomposition schemes.