Data Structures for Mergeable Trees
Φόρτωση...
Ημερομηνία
Συγγραφείς
Georgiadis, L.
Kaplan, H.
Shafrir, N.
Tarjan, R. E.
Werneck, R. F.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Acm Transactions on Algorithms
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Motivated by an application in computational geometry, we consider a novel variant of the problem of efficiently maintaining a forest of dynamic rooted trees. This variant includes an operation that merges two tree paths. In contrast to the standard problem, in which a single operation can only add or delete one arc, one merge can add and delete up to a linear number of arcs. In spite of this, we develop three different methods that need only polylogarithmic time per operation. The first method extends a solution of Farach and Thorup [1998] for the special case of paths. Each merge takes O(log(2) n) amortized time on an n-node forest and each standard dynamic tree operation takes O(log n) time; the latter bound is amortized, worst case, or randomized depending on the underlying data structure. For the special case that occurs in the motivating application, in which arbitrary arc deletions (cuts) do not occur, we give a method that takes O(log n) time per operation, including merging. This is best possible in a model of computation with an Omega(nlog n) lower bound for sorting n numbers, since such sorting can be done in O(n) tree operations. For the even-more-special case in which there are no cuts and no parent queries, we give a method that uses standard dynamic trees as a black box: each mergeable tree operation becomes a constant number of standard dynamic tree operations. This third method can also be used in the motivating application, but only by changing the algorithm in the application. Each of our three methods needs different analytical tools and reveals different properties of dynamic trees.
Περιγραφή
Λέξεις-κλειδιά
amortized efficiency, computational topology, critical pairs, dynamic trees, extreme points, link-cut trees, manifolds, merging, dynamic trees, search-trees, algorithm
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής