Carregant...
Carregant...

Vés al contingut (premeu Retorn)

An algebraic view of the relation between largest common subtrees and smallest common supertrees

Autor
Francesc, R.; Valiente, G.
Tipus d'activitat
Article en revista
Revista
Theoretical computer science
Data de publicació
2006-01
Volum
362
Número
1-3
Pàgina inicial
33
Pàgina final
53
DOI
https://doi.org/10.1016/j.tcs.2006.05.031 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S0304397506003173?via%3Dihub Obrir en finestra nova
Resum
The relationship between two important problems in tree pattern matching, the largest common subtree and the smallest common supertree problems, is established by means of simple constructions, which allow one to obtain a largest common subtree of two trees from a smallest common supertree of them, and vice versa. These constructions are the same for isomorphic, homeomorphic, topological, and minor embeddings, they take only time linear in the size of the trees, and they turn out to have a clear...
Paraules clau
Largest common subtree, Minor containment, Smallest common supertree, Subtree homeomorphismTopological embedding, Subtree isomorphism, Tree pattern matching
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants