Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/5596

Isomorphism testing and display of symmetries in dynamic trees

Authors Ng, Moon-pun
Issue Date 1995
Summary We describe data structures for maintaining a set of trees so that isomorphism testing for any two trees can be performed in O(1) time. Updates include inserting an edge to merge two trees or removing an edge to split a tree into two smaller trees. Each update can be performed in O(log2nlogm log*m) time, where n is the total size of trees involved and m is the number of updates performed so far. The space needed per update is O(logn logm log*m). We apply this result to display symmetries in dynamic free trees. A framework for dynamic symmetric drawing of free trees is developed, which supports the drawing of subtrees in an output-sensitive manner.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1995
Subjects
Language English
Format Thesis
Access
Files in this item:
File Description Size Format
th_redirect.html 341 B HTML