Computer Science – Data Structures and Algorithms
Scientific paper
2006-08-31
Computer Science
Data Structures and Algorithms
Minor updates from last time
Scientific paper
Given two rooted, ordered, and labeled trees $P$ and $T$ the tree inclusion problem is to determine if $P$ can be obtained from $T$ by deleting nodes in $T$. This problem has recently been recognized as an important query primitive in XML databases. Kilpel\"ainen and Mannila [\emph{SIAM J. Comput. 1995}] presented the first polynomial time algorithm using quadratic time and space. Since then several improved results have been obtained for special cases when $P$ and $T$ have a small number of leaves or small depth. However, in the worst case these algorithms still use quadratic time and space. Let $n_S$, $l_S$, and $d_S$ denote the number of nodes, the number of leaves, and the %maximum depth of a tree $S \in \{P, T\}$. In this paper we show that the tree inclusion problem can be solved in space $O(n_T)$ and time: O(\min(l_Pn_T, l_Pl_T\log \log n_T + n_T, \frac{n_Pn_T}{\log n_T} + n_{T}\log n_{T})). This improves or matches the best known time complexities while using only linear space instead of quadratic. This is particularly important in practical applications, such as XML databases, where the space is likely to be a bottleneck.
Bille Philip
Goertz Inge Li
No associations
LandOfFree
The Tree Inclusion Problem: In Linear Space and Faster does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Tree Inclusion Problem: In Linear Space and Faster, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Tree Inclusion Problem: In Linear Space and Faster will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-396939