An Algebraic View of the Relation between Largest Common Subtrees and Smallest Common Supertrees

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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 algebraic meaning.
32 pages

Keywords

Data Structures and Algorithms, Discrete Mathematics, Category Theory, G.2.3

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/111061

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0604108
 http://arxiv.org/abs/cs/0604108

Collections

arXiv