Survey on Subtree Matching

The subtree matching is the problem of finding all the matching occurrences of a pattern tree in a subject tree as a subtree. This paper introduces many problems that are related to subtree matching and provides a classification of them. The basic problem has got several variations depending on the type of trees and on what we call a match. Trees can be rooted or unrooted, ordered and unordered and labeled or unlabeled. A subtree matching may mean subtree isomorphism, subtree homeomorphism, subtree inclusion or pattern matching. This paper introduces the most important algorithms for these problems while paying special attention to their complexities