HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses  >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/5596
Title: Isomorphism testing and display of symmetries in dynamic trees
Authors: Ng, Moon-pun
Issue Date: 1995
Abstract: 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.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1995
ix, 53 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 1995 NgMP
URI: http://hdl.handle.net/1783.1/5596
Appears in Collections:CSE Master Theses

Files in This Item:

File Description SizeFormat
th_redirect.html0KbHTMLView/Open

All items in this Repository are protected by copyright, with all rights reserved.