“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 10h30.
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.