TY - GEN
T1 - Dynamic trees in practice
AU - Tarjan, Robert E.
AU - Werneck, Renato F.
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=37149052526&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=37149052526&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-72845-0_7
DO - 10.1007/978-3-540-72845-0_7
M3 - Conference contribution
AN - SCOPUS:37149052526
SN - 3540728449
SN - 9783540728443
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 80
EP - 93
BT - Experimental Algorithms - 6th International Workshop, WEA 2007, Proceedings
PB - Springer Verlag
T2 - 6th International Workshop on Experimental Algorithms, WEA 2007
Y2 - 6 June 2007 through 8 June 2007
ER -