Parallel and Distributed Systems Group

Computer Science Department of Telecom SudParis

“Non-blocking Dynamic Unbounded Graphs with Worst-case Amortized Bounds” DISC’21

Team work: Muktikanta Sa presented ""Non-blocking Dynamic Unbounded Graphs with Worst-case Amortized Bounds" DISC'21" (DISC'21) at 4A312 the 24/9/2021 at 10h00.

Abstract

This paper reports a new concurrent graph data structure that supports updates of both edges and vertices and queries: Breadth-first search, Single-source shortest-path, and Betweenness centrality. The operations are provably linearizable and non-blocking.