Short Paper: Maintenance of Strongly Connected Component in Shared-Memory Graph

Sa, Muktikanta (2019) Short Paper: Maintenance of Strongly Connected Component in Shared-Memory Graph. In: International Conference on Networked Systems, NETYS, 9-11 May 2018, Morocco.

Full text not available from this repository. (Request a copy)

Abstract

In this paper, we present an on-line fully dynamic algorithm for maintaining strongly connected component of a directed graph in a shared memory architecture. The edges and vertices are added or deleted concurrently by fixed number of threads. To the best of our knowledge, this is the first work to propose using linearizable concurrent directed graph and is build using both ordered and unordered list-based set. We provide an empirical comparison against sequential and coarse-grained. The results show our algorithm’s throughput is increased between 3 to 6x depending on different workload distributions and applications. We believe that there are huge applications in the on-line graph. Finally, we show how the algorithm can be extended to community detection in on-line graph.

[error in script]

IITH Creators:	IITH Creators ORCiD
Item Type:	Conference or Workshop Item (Paper)
Uncontrolled Keywords:	Concurrent data structure, Connectivity on directed graphs, Directed graph, Dynamic graph algorithms, Strong connected components
Subjects:	Computer science
Divisions:	Department of Computer Science & Engineering
Depositing User:	Team Library
Date Deposited:	29 Jan 2019 11:57
Last Modified:	29 Jan 2019 11:57
URI:	http://raiithold.iith.ac.in/id/eprint/4773
Publisher URL:	http://doi.org/10.1007/978-3-030-05529-5_27
Related URLs:	Google Scholar

Actions (login required)

View Item

Statistics for this ePrint Item