IJPAM: Volume 38, No. 3 (2007)

BOTTOM-UP SUBTREE ISOMORPHISM FOR
UNORDERED LABELED TREES

Fabrizio Luccio$^1$, Linda Pagli$^2$, Antonio Mesa Enriquez$^3$,
Pablo Olivares Rieumont$^4$
$^{1,2}$Department of Informatics
University of Pisa
Largo B. Pontecorvo 3, Pisa, 56127, ITALY
$^1$e-mail: luccio@di.unipi.it
$^2$e-mail: pagli@di.unipi.it
$^{3,4}$Faculty of Mathematics and Computation
University of Habana
San Làzaro y L, La Habana, CUBA
$^3$e-mail: tonymesa@matcom.uh.cu
$^4$e-mail: olivares@matcom.uh.cu


Abstract.A bottom-up subtree $P$ of a labeled unordered tree $T$ is such that, for each internal vertex $u$ of $P$, all the children of $u$ in $T$ are also vertices of $P$, and the labels in corresponding positions also match. We aim to finding all the occurrences of a pattern tree $P$ of $m$ vertices as a bottom-up subtree of a text tree $T$ of $n$ vertices, $m\leq n$. If the labels are single characters of a constant or of an n-integer alphabet $\Sigma$, the problem is solved in $O(m +\log n)$ time and $\Theta(m)$ additional space, after a preprocessing of $T$ is done in $\Theta(n)$ time and $\Theta(n)$ additional space. Note that the number of occurrences of $P$ in $T$ does not appear in the search time. For more complex labels the running times increase, becoming a function of the total length of all the labels in $T$ and $P$ if such labels are sequences of characters. Regarding $T$ as a static text and $P$ as the contents of a query on $T$, and assuming $m=o(n)$, the response time for each $P$ is sublinear in the size of the overall structure.

Received: March 29, 2007

AMS Subject Classification: 68C05

Key Words and Phrases: rooted tree, bottom-up subtree, subtree isomorphism, tree pattern matching, design of algorithms

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2007
Volume: 38
Issue: 3