@inproceedings{c50c5cf4e5724598a2750c59dc90479c,
title = "Brief announcement: Parallel dynamic tree contraction via self-adjusting computation",
abstract = "Dynamic algorithms are used to compute a property of some data while the data undergoes changes over time. Many dynamic algorithms have been proposed but nearly all are sequential. In this paper, we present our ongoing work on designing a parallel algorithm for the dynamic trees problem, which requires computing a property of a forest as the forest undergoes changes. Our algorithm allows insertion and/or deletion of both vertices and edges anywhere in the input and performs updates in parallel. We obtain our algorithm by applying a dynamization technique called self-adjusting computation to the classic algorithm of Miller and Reif for tree contraction.",
author = "Acar, {Umut A.} and Vitaly Aksenov and Sam Westrick",
note = "Publisher Copyright: {\textcopyright} 2017 Copyright held by the owner/author(s).; 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017 ; Conference date: 24-07-2017 Through 26-07-2017",
year = "2017",
month = jul,
day = "24",
doi = "10.1145/3087556.3087595",
language = "English (US)",
series = "Annual ACM Symposium on Parallelism in Algorithms and Architectures",
publisher = "Association for Computing Machinery",
pages = "275--277",
booktitle = "SPAA 2017 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures",
}