View Full Document

# Alogtime Algorithms

View Full Document
View Full Document

6 views

Unformatted text preview:

Alogtime Algorithms for Tree Isomorphism Comparison and Canonization Samuel R Buss Departments of Mathematics Computer Science Univ of California San Diego La Jolla CA 92093 0112 Abstract The tree isomorphism problem is the problem of determining whether two trees are isomorphic The tree canonization problem is the problem of producing a canonical tree isomorphic to a given tree The tree comparison problem is the problem of determining whether one tree is less than a second tree in a natural ordering on trees We present alternating logarithmic time algorithms for the tree isomorphism problem the tree canonization problem and the tree comparison problem As a consequence there is a recursive enumeration of the alternating log time tree problems 1 Introduction A tree is a finite connected acyclic graph with a distinguished root node An isomorphism between two trees T1 and T2 is a bijection between the nodes of T1 and the nodes of T2 which preserves the edges and which maps the root of T1 to the root of T2 Two trees are isomorphic if there is an isomorphism between them An implicit component of our definition of isomorphism is that the children of a node in a tree are unordered Of course whenever a tree is drawn or especially is represented in on a computer there is an ordering specified by the representation of the tree For instance we define a string representation of trees below and any string representation of a tree orders the subtrees and nodes of T This means of course that a given tree may have many different representations The question of whether two different string representations are representations of the same tree is called the tree isomorphism problem One way to solve the isomorphism is define canonical representations for trees in such way that every unordered tree has exactly one canonical representations The problem of converting an arbitrary string representation of a tree into a canonical representation is called the tree canonization problem In

## Access the best Study Guides, Lecture Notes and Practice Exams Unlocking...