The ACM Journal of Experimental Algorithmics

We describe an implementation of dynamic trees with "in-subtree" operations. Our implementation follows Sleator and Tarjan's framework of dynamic-tree implementations based on splay trees. We consider the following two examples of "in-subtree" operations: (a) for a given node v, find a node with the minimum key in the subtree rooted at v; and (b) for a given node v, find a random node with key X in the subtree rooted at v (value X is fixed throughout the whole computation). The first operation may provide support for edge deletions in the dynamic minimum spanning tree problem. The second one may be useful in local search methods for degree-constrained minimum spanning tree problems. We conducted experiments with our dynamic-tree implementation within these two contexts, and the results suggest that this implementation may lead to considerably faster codes than straightforward approaches.

• Keywords: Dynamic trees, Splay trees, Dynamic minimum spanning trees, Experimentation, Performance
• CR Categories: G.4 [Mathematical Software]: Algorithm Design and Analysis, Efficiency; G.2.2 [Graph Theory]: Graph Algorithms, Network Problems, Trees
• Sources:
  NOTE: this article is undergoing some last-minute minor revisions and will be available shortly.
  • The LaTeX version of the article; this is a Unix tar file that contains the LaTeX sources; note that you must be a subscriber (institutional or individual) to access this file.
  • The Postscript version or PDF version of the article;
    note that you must be a subscriber (institutional or individual) to access these files.
  • The HTML version of the article;
    note that you must be a subscriber (institutional or individual) to access this file.
  • The software suite accompanying the article; this is a small Unix tar file, which includes the source code, a Makefile, and the test files used in the article.
  • The bibliography given in the article.

Last updated and validated March 30, 1999, by editor@jea.acm.org