Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds
Chatterjee B, Peri S, Sa M. 2021. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 52.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
Chatterjee, BapiISTA;
Peri, Sathya;
Sa, Muktikanta
Department
Series Title
LIPIcs
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.
Publishing Year
Date Published
2021-10-04
Proceedings Title
35th International Symposium on Distributed Computing
Acknowledgement
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).
Volume
209
Article Number
52
Conference
DISC: Distributed Computing
Conference Location
Freiburg, Germany
Conference Date
2021-10-04 – 2021-10-08
ISBN
ISSN
IST-REx-ID
Cite this
Chatterjee B, Peri S, Sa M. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. In: 35th International Symposium on Distributed Computing. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.DISC.2021.52
Chatterjee, B., Peri, S., & Sa, M. (2021). Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. In 35th International Symposium on Distributed Computing (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.52
Chatterjee, Bapi, Sathya Peri, and Muktikanta Sa. “Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” In 35th International Symposium on Distributed Computing, Vol. 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.52.
B. Chatterjee, S. Peri, and M. Sa, “Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds,” in 35th International Symposium on Distributed Computing, Freiburg, Germany, 2021, vol. 209.
Chatterjee B, Peri S, Sa M. 2021. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 52.
Chatterjee, Bapi, et al. “Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” 35th International Symposium on Distributed Computing, vol. 209, 52, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.DISC.2021.52.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2021_LIPIcsDISC_BChatterjee.pdf
795.86 KB
Access Level
Open Access
Date Uploaded
2021-11-12
MD5 Checksum
76546df112a0ba1166c864d33d7834e2
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2003.01697
Google Scholar
ISBN Search