Tree inclusion problems
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 5-20.

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).

DOI : https://doi.org/10.1051/ita:2007052
Classification : 68Q25,  68W05
Mots clés : subtree inclusion, algorithm
@article{ITA_2008__42_1_5_0,
     author = {C\'egielski, Patrick and Guessarian, Ir\`ene and Matiyasevich, Yuri},
     title = {Tree inclusion problems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {5--20},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {1},
     year = {2008},
     doi = {10.1051/ita:2007052},
     zbl = {1149.68040},
     mrnumber = {2382541},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2007052/}
}
TY  - JOUR
AU  - Cégielski, Patrick
AU  - Guessarian, Irène
AU  - Matiyasevich, Yuri
TI  - Tree inclusion problems
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
DA  - 2008///
SP  - 5
EP  - 20
VL  - 42
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007052/
UR  - https://zbmath.org/?q=an%3A1149.68040
UR  - https://www.ams.org/mathscinet-getitem?mr=2382541
UR  - https://doi.org/10.1051/ita:2007052
DO  - 10.1051/ita:2007052
LA  - en
ID  - ITA_2008__42_1_5_0
ER  - 
Cégielski, Patrick; Guessarian, Irène; Matiyasevich, Yuri. Tree inclusion problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 5-20. doi : 10.1051/ita:2007052. http://www.numdam.org/articles/10.1051/ita:2007052/

[1] L. Boasson, P. Cegielski, I. Guessarian and Yu. Matiyasevich, Window accumulated subsequence matching is linear. Ann. Pure Appl. Logic 113 (2001) 59-80. | MR 1875736 | Zbl 0998.68042

[2] Y. Chi, R. Muntz, S. Nijssen and J. Kok, Frequent subtree mining - an overview. Fund. Inform. 66 (2005) 161-198. | MR 2347731 | Zbl 1096.68044

[3] P. Kilpelainen, Tree matching problems with applications to structured text databases. Ph.D. thesis, Helsinki (1992). http://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. | MR 1320214 | Zbl 0827.68050

Cité par Sources :