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.

Text
Leibniz .pdf - Published Version
Available under License Creative Commons Attribution.
Download (795kB)

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

[error in script]

IITH Creators:

IITH Creators	ORCiD
Peri, Sathya	UNSPECIFIED

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