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.
Type de document :
Communication dans un congrès
The 29th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '17), Jul 2017, Washington, United States. 〈10.1145/3087556.3087595〉
Liste complète des métadonnées

Littérature citée [42 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01664903
Contributeur : Vitalii Aksenov <>
Soumis le : vendredi 15 décembre 2017 - 12:31:35
Dernière modification le : jeudi 26 avril 2018 - 10:27:45

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Umut Acar, Vitalii Aksenov, Sam Westrick. Brief Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation. The 29th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '17), Jul 2017, Washington, United States. 〈10.1145/3087556.3087595〉. 〈hal-01664903〉

Partager

Métriques

Consultations de la notice

88

Téléchargements de fichiers

46