Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/11060Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Georgiadis, L. | en |
| dc.contributor.author | Kaplan, H. | en |
| dc.contributor.author | Shafrir, N. | en |
| dc.contributor.author | Tarjan, R. E. | en |
| dc.contributor.author | Werneck, R. F. | en |
| dc.date.accessioned | 2015-11-24T17:02:29Z | - |
| dc.date.available | 2015-11-24T17:02:29Z | - |
| dc.identifier.issn | 1549-6325 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/11060 | - |
| dc.rights | Default Licence | - |
| dc.subject | amortized efficiency | en |
| dc.subject | computational topology | en |
| dc.subject | critical pairs | en |
| dc.subject | dynamic trees | en |
| dc.subject | extreme points | en |
| dc.subject | link-cut trees | en |
| dc.subject | manifolds | en |
| dc.subject | merging | en |
| dc.subject | dynamic trees | en |
| dc.subject | search-trees | en |
| dc.subject | algorithm | en |
| dc.title | Data Structures for Mergeable Trees | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | Doi 10.1145/1921659.1921660 | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2011 | - |
| heal.abstract | 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. | en |
| heal.journalName | Acm Transactions on Algorithms | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Georgiadis-2011-Data Structures for.pdf | 777.79 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
