Ordered and unordered tree inclusion. (English) Zbl 0827.68050

Summary: The following tree-matching problem is considered: Given labeled trees \(P\) and \(T\), can \(P\) be obtained from \(T\) by deleting nodes? Deleting a node \(u\) entails removing all edges incident to \(u\) and, if \(u\) has a parent \(v\), replacing the edge from \(v\) to \(u\) by edges from \(v\) to the children of \(u\). The problem is motivated by the study of query languages for structured text databases. Simple solutions to this problem require exponential time. For ordered trees an algorithm is presented that requires \(O(|P||T|)\) time and space. The corresponding problem for unordered trees is also considered and a proof of its NP- completeness is given. An algorithm is presented for the unordered problem. This algorithm works in \(O(|P||T|)\) time if the out-degrees of the nodes in \(P\) are bounded by a constant, and in polynomial time if they are \(O(\log |T|)\).


68W10 Parallel algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
68P15 Database theory
Full Text: DOI