# Tree inclusion problems

Patrick Cégielski; Irène Guessarian; Yuri Matiyasevich

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 42, Issue: 1, page 5-20
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCégielski, Patrick, Guessarian, Irène, and Matiyasevich, Yuri. "Tree inclusion problems." RAIRO - Theoretical Informatics and Applications 42.1 (2008): 5-20. <http://eudml.org/doc/250322>.

@article{Cégielski2008,

abstract = {
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|22|P|) where |T| (resp. |P|) is the size of T (resp. P).
},

author = {Cégielski, Patrick, Guessarian, Irène, Matiyasevich, Yuri},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Subtree inclusion; algorithm; window embedded subtree problems},

language = {eng},

month = {1},

number = {1},

pages = {5-20},

publisher = {EDP Sciences},

title = {Tree inclusion problems},

url = {http://eudml.org/doc/250322},

volume = {42},

year = {2008},

}

TY - JOUR

AU - Cégielski, Patrick

AU - Guessarian, Irène

AU - Matiyasevich, Yuri

TI - Tree inclusion problems

JO - RAIRO - Theoretical Informatics and Applications

DA - 2008/1//

PB - EDP Sciences

VL - 42

IS - 1

SP - 5

EP - 20

AB -
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|22|P|) where |T| (resp. |P|) is the size of T (resp. P).

LA - eng

KW - Subtree inclusion; algorithm; window embedded subtree problems

UR - http://eudml.org/doc/250322

ER -

## References

top- L. Boasson, P. Cegielski, I. Guessarian and Yu. Matiyasevich, Window accumulated subsequence matching is linear. Ann. Pure Appl. Logic113 (2001) 59–80. Zbl0998.68042
- Y. Chi, R. Muntz, S. Nijssen and J. Kok, Frequent subtree mining – an overview. Fund. Inform.66 (2005) 161–198. Zbl1096.68044
- 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/
- P. Kilpelainen and H. Mannila, Ordered and unordered tree inclusion. SIAM J. Comput.24 (1995) 340–356. Zbl0827.68050

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.