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
Publisher
Schloss Dagstuhl - Leibniz Zentrum für Informatik
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