✦ LIBER ✦

A Data Structure for Dynamically Maintaining Rooted Trees

✍ Scribed by Greg N. Frederickson

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 274 KB
Volume: 24
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1996.0835

No coin nor oath required. For personal study only.

✦ Synopsis

The directed topology tree data structure is developed for maintaining binary trees dynamically. Each of a certain set of tree operations is shown to take Ž . Olog n time, where n is the number of vertices in the trees. The directed topology trees are used to implement link᎐cut trees and dynamic expression trees. The results of experimental comparisons with the dynamic trees of Sleator and Tarjan are presented.

📜 SIMILAR VOLUMES

Fully Dynamic Algorithms for Maintaining

Fully Dynamic Algorithms for Maintaining Shortest Paths Trees

✍ Daniele Frigioni; Alberto Marchetti-Spaccamela; Umberto Nanni 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 213 KB

We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal quer

A network flow approach to cost allocati

A network flow approach to cost allocation for rooted trees

✍ Satoru Iwata; Nozomu Zuiki 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

On digraphs with a rooted tree structure

✍ Jayme L. Szwarcfiter 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB

An Efficient Method for Version Control

An Efficient Method for Version Control of a Tree Data Structure

✍ ESTHER JINEE CHOI; YONG RAE KWON 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB 👁 1 views

A new method for version controlling of a tree structure is presented. The key feature of the method is that the latest state of a tree is retained and other versions are constructed from it on request, and information on the change history of a node is maintaind in its parent node. Several algorith

A Performance Comparison of Tree Data St

A Performance Comparison of Tree Data Structures for N-Body Simulation

✍ J. Waltz; G.L. Page; S.D. Milder; J. Wallin; A. Antunes 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 137 KB

We present a performance comparison of tree data structures for N -body simulation. The tree data structures examined are the balanced binary tree and the Barnes-Hut (BH) tree. Previous work has compared the performance of BH trees with that of nearest-neighbor trees and the fast multipole method, b

The Characterization of Topology: A Comp

The Characterization of Topology: A Comparison of Four topological Indices for Rooted Binary Trees

✍ G.M. Berntson 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 388 KB

The quantification of the topological features of binary trees has been applied in several branches of biology, from botany to neurobiology to animal behaviour. The methods available for quantifying tree topology differ, both in how they are applied and how they relate to one another. In this paper,