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

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

2006-04-27

arxiv.org/abs/cs/0604108v1

Computer Science

Data Structures and Algorithms

32 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

An Algebraic View of the Relation between Largest Common Subtrees and Smallest Common Supertrees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Algebraic View of the Relation between Largest Common Subtrees and Smallest Common Supertrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Algebraic View of the Relation between Largest Common Subtrees and Smallest Common Supertrees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-20648