The Tree Inclusion Problem: In Linear Space and Faster

Publication: Research - peer-reviewJournal article – Annual report year: 2011

View graph of relations

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 äinen and Mannila [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 nS, lS, and dS denote the number of nodes, the number of leaves, and the depth of a tree S ε {P, T}. In this article we show that the tree inclusion problem can be solved in space O(nT ) and time: Eqation Presented ∑ 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. © 2011 ACM.
Original languageEnglish
JournalA C M Transactions on Algorithms
Publication date2011
Volume7
Issue3
Pages38
ISSN1549-6325
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 0
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 6237745