skip to main content
research-article

Dynamic trees in practice

Published: 05 January 2010 Publication History

Abstract

Dynamic tree data structures maintain forests that change over time through edge insertions and deletions. Besides maintaining connectivity information in logarithmic time, they can support aggregation of information over paths, trees, or both. We perform an experimental comparison of several versions of dynamic trees: ST-trees, ET-trees, RC-trees, and two variants of top trees (self-adjusting and worst-case). We quantify their strengths and weaknesses through tests with various workloads, most stemming from practical applications. We observe that a simple, linear-time implementation is remarkably fast for graphs of small diameter, and that worst-case and randomized data structures are best when queries are very frequent. The best overall performance, however, is achieved by self-adjusting ST-trees.

References

[1]
Acar, U. A., Blelloch, G. E., Harper, R., Vittes, J. L., and Woo, S. L. M. 2004. Dynamizing static algorithms, with applications to dynamic trees and history independence. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04). SIAM, Philadelphia, 524--533.
[2]
Acar, U. A., Blelloch, G. E., and Vittes, J. L. 2005. An experimental analysis of change propagation in dynamic trees. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05). SIAM, Philadelphia, 41--54.
[3]
Addario-Berry, L., Broutin, N., and Reed, B. 2006. The diameter of the minimum spanning tree of a complete graph. In Proceedings of the 4th Colloquium on Mathematics and Computer Science. Discrete Mathematics and Theoretical Computer Science, Nancy, France, 237--248.
[4]
Ahuja, R., Magnanti, T., and Orlin, J. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Upper Saddle River, NJ.
[5]
Alstrup, S., Holm, J., de Lichtenberg, K., and Thorup, M. 1997. Minimizing diameters of dynamic trees. In Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP'97). Springer, Berlin, 270--280.
[6]
Alstrup, S., Holm, J., and Thorup, M. 1999. On the power and speed of top trees. Unpublished manuscript.
[7]
Alstrup, S., Holm, J., Thorup, M., and de Lichtenberg, K. 2005. Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms 1, 2, 243--264.
[8]
Anderson, R. 1993. The Washington graph generator. In DIMACS Series in Discrete Mathematics and Computer Science, D. S. Johnson and C. C. McGeoch, Eds. AMS, 580--581.
[9]
Bellman, R. 1958. On a routing problem. Q. Math. 16, 87--90.
[10]
Cattaneo, G., Faruolo, P., Ferraro-Petrillo, U., and Italiano, G. F. 2002. Maintaining dynamic minimum spanning trees: An experimental study. In Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX'02). Springer, Berlin, 111--125.
[11]
Cherkassky, B. V., Georgiadis, L., Goldberg, A. V., Tarjan, R. E., and Werneck, R. F. 2008. Shortest path feasibility algorithms: An experimental evaluation. In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'08). SIAM, Philadelphia, 118--132.
[12]
Cherkassky, B. V. and Goldberg, A. V. 1999. Negative-cycle detection algorithms. Math. Program. 85, 277--311.
[13]
Dinic, E. A. 1970. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Mathematics Doklady 11, 1277--1280.
[14]
Edmonds, J. and Karp, R. M. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 248--264.
[15]
Ford, Jr., L. 1956. Network flow theory. Tech. rep. P-932, The Rand Corporation.
[16]
Frederickson, G. N. 1985. Data structures for online update of minimum spanning trees, with applications. SIAM J. Comput. 14, 4, 781--798.
[17]
Frederickson, G. N. 1997a. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput. 26, 2, 484--538.
[18]
Frederickson, G. N. 1997b. A data structure for dynamically maintaining rooted trees. J. Algorithms 24, 1, 37--65.
[19]
Goldberg, A. V., Grigoriadis, M. D., and Tarjan, R. E. 1991. Use of dynamic trees in a network simplex algorithm for the maximum flow problem. Math. Program. 50, 277--290.
[20]
Henzinger, M. R. and King, V. 1997. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC'97). ACM, New York, 519--527.
[21]
Kaplan, H., Molad, E., and Tarjan, R. E. 2003. Dynamic rectangular intersection with priorities. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC'03). ACM, New York, 639--648.
[22]
Klein, P. N. 2005. Multiple-source shortest paths in planar graphs. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05). ACM, New York, 146--155.
[23]
Langerman, S. 2000. On the shooter location problem: Maintaining dynamic circular-arc graphs. In Proceedings of the 12th Canadian Conference on Computational Geometry (CCCG'00). 29--35.
[24]
Miller, G. L. and Reif, J. H. 1985. Parallel tree contraction and its applications. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science (FOCS'85). IEEE, Los Alamitos, CA, 478--489.
[25]
Moore, E. F. 1959. The shortest path through a maze. In Proceedings of the International Symposium on the Theory of Switching. Harvard University Press, Cambridge, MA, 285--292.
[26]
Radzik, T. 1998. Implementation of dynamic trees with in-subtree operations. ACM J. Exp. Algorithmics 3, 9.
[27]
Ribeiro, C. C. and Toso, R. F. 2007. Experimental analysis of algorithms for updating minimum spanning trees on graphs subject to changes on edge weights. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Springer, Berline, 393--405.
[28]
Sleator, D. D. and Tarjan, R. E. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 3, 362--391.
[29]
Sleator, D. D. and Tarjan, R. E. 1985. Self-adjusting binary search trees. J. ACM 32, 3, 652--686.
[30]
Tarjan, R. E. 1983. Data Structures and Network Algorithms. SIAM, Philadelphia.
[31]
Tarjan, R. E. 1997. Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math. Program. 78, 169--177.
[32]
Tarjan, R. E. and Werneck, R. F. 2005. Self-adjusting top trees. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05). ACM, New York, 813--822.
[33]
Werneck, R. F. 2006. Design and analysis of data structures for dynamic trees. Ph.D. thesis, Princeton University.
[34]
Zaroliagis, C. D. 2002. Implementations and experimental studies of dynamic graph algorithms. In Experimental Algorithms: From Algorithm Design to Robust and Efficient Software, R. Fleischer, B. Moret, and E. M. Schmidt, Eds. Lecture Notes in Computer Science. Springer, Berlin, 229--278.

Cited By

View all
  • (2024)Implementing the Link‐Cut TreeSoftware: Practice and Experience10.1002/spe.3393Online publication date: 8-Dec-2024
  • (2022)Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference GuideACM Journal of Experimental Algorithmics10.1145/355580627(1-45)Online publication date: 13-Dec-2022
  • (2019)Separable Convex Optimization with Nested Lower and Upper ConstraintsINFORMS Journal on Optimization10.1287/ijoo.2018.00041:1(71-90)Online publication date: Jan-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics
ACM Journal of Experimental Algorithmics  Volume 14, Issue
2009
613 pages
ISSN:1084-6654
EISSN:1084-6654
DOI:10.1145/1498698
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 January 2010
Accepted: 01 July 2009
Received: 01 March 2009
Published in JEA Volume 14

Author Tags

  1. Dynamic trees
  2. experimental evaluation
  3. link-cut trees
  4. top trees

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)54
  • Downloads (Last 6 weeks)5
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Implementing the Link‐Cut TreeSoftware: Practice and Experience10.1002/spe.3393Online publication date: 8-Dec-2024
  • (2022)Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference GuideACM Journal of Experimental Algorithmics10.1145/355580627(1-45)Online publication date: 13-Dec-2022
  • (2019)Separable Convex Optimization with Nested Lower and Upper ConstraintsINFORMS Journal on Optimization10.1287/ijoo.2018.00041:1(71-90)Online publication date: Jan-2019
  • (2017)Brief AnnouncementProceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3087556.3087595(275-277)Online publication date: 24-Jul-2017
  • (2016)Dynamic Subtrees Queries Revisited: The Depth First Tour TreeCombinatorial Algorithms10.1007/978-3-319-29516-9_13(148-160)Online publication date: 20-Feb-2016
  • (2013)Dynamic graph connectivity in polylogarithmic worst case timeProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627898(1131-1142)Online publication date: 6-Jan-2013
  • (2013)A Deterministic $$O(m \log {m})$$O(mlogm) Time Algorithm for the Reeb GraphDiscrete & Computational Geometry10.1007/s00454-013-9511-349:4(864-878)Online publication date: 1-Jun-2013
  • (2013)Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with monge costsNetworks10.1002/net.2150762:2(136-148)Online publication date: 28-May-2013
  • (2012)A deterministic o(m log m) time algorithm for the reeb graphProceedings of the twenty-eighth annual symposium on Computational geometry10.1145/2261250.2261289(269-276)Online publication date: 17-Jun-2012
  • (2012)Fast local search for the steiner problem in graphsACM Journal of Experimental Algorithmics10.1145/2133803.218444817(2.1-2.22)Online publication date: 22-May-2012
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media