Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds

Chatterjee, Bapi and Peri, Sathya and Sa, Muktikanta (2021) Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds. In: 35th International Symposium on Distributed Computing, DISC 2021, 4 October 2021 through 8 October 2021, Virtual, Freiburg.

[img] Text
Leibniz .pdf - Published Version
Available under License Creative Commons Attribution.

Download (795kB)


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. © Bapi Chatterjee, Sathya Peri, and Muktikanta Sa; licensed under Creative Commons License CC-BY 4.0

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Conference or Workshop Item (Paper)
Additional Information: Funding This work was partially funded by National Supercomputing Mission, Govt. of India under the project “Concurrent and Distributed Programming primitives and algorithms for Temporal Graphs”(DST/NSM/R&D_Exascale/2021/16).
Uncontrolled Keywords: Betweenness centrality; Breadth-first search; Concurrent data structure; Directed graph; Linearizability; Non-blocking; Single-source shortest-path
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 08 Aug 2022 06:33
Last Modified: 08 Aug 2022 06:33
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 10126 Statistics for this ePrint Item