Tree inclusion problems. (English) Zbl 1149.68040

Summary: Given two trees (a target \(T\) and a pattern \(P\)) and a natural number \(w\), window embedded subtree problems consist in deciding whether \(P\) occurs as an embedded subtree of \(T\) and/or finding the number of size (at most) \(w\) windows of \(T\) which contain pattern \(P\) as an embedded subtree. \(P\) is an embedded subtree of \(T\) if \(P\) can be obtained by deleting some nodes from \(T\) (if a node \(v\) is deleted, all edges adjacent to \(v\) are also deleted, and outgoing edges are replaced by edges going from the parent of \(v\) (if it exists) to the children of \(v\)). Deciding whether \(P\) is an embedded subtree of \(T\) is known to be NP-complete. Our algorithms run in time \(O(|T|2^{2^{|P|}} )\) where \(|T|\) (resp. \(|P|\)) is the size of \(T\) (resp. \(P\)).


68Q25 Analysis of algorithms and problem complexity
68W05 Nonnumerical algorithms
Full Text: DOI EuDML Link


[1] L. Boasson, P. Cegielski, I. Guessarian and Yu. Matiyasevich, Window accumulated subsequence matching is linear. Ann. Pure Appl. Logic113 (2001) 59-80. · Zbl 0998.68042
[2] Y. Chi, R. Muntz, S. Nijssen and J. Kok, Frequent subtree mining - an overview. Fund. Inform.66 (2005) 161-198. · Zbl 1096.68044
[3] P. Kilpelainen, Tree matching problems with applications to structured text databases. Ph.D. thesis, Helsinki (1992). URIhttp://ethesis.helsinki.fi/julkaisut/mat/tieto/vk/kilpelainen/
[4] P. Kilpelainen and H. Mannila, Ordered and unordered tree inclusion. SIAM J. Comput.24 (1995) 340-356. Zbl0827.68050 · Zbl 0827.68050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.