Maintenance of Strongly Connected Component in Shared-memory Graph

Preprint English OPEN
Sa, Muktikanta;
  • Subject: Computer Science - Distributed, Parallel, and Cluster Computing

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 knowled... View more
  • References (17)
    17 references, page 1 of 2

    1. David A. Bader, Jonathan W. Berry, Daniel Chavarr a-Miranda, Kamesh Madduri, and Steven C. Poulos. Stinger: Spatio-temporal interaction networks and graphs (sting) extensible representation. 2009.

    2. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan. A New Approach to Incremental Cycle Detection and Related Problems. ACM Trans. Algorithms, 12(2):14, 2016. URL:, doi:10.1145/2756553.

    3. Vincent Bloemen, Alfons Laarman, and Jaco van de Pol. Multi-core on-they scc decomposition. SIGPLAN Not., 51(8):8:1{8:12, February 2016. URL:, doi:10.1145/3016078.2851161.

    4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cli ord Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009. URL: edu/books/introduction-algorithms.

    5. Camil Demetrescu, David Eppstein, Zvi Galil, and Giuseppe F. Italiano. In Mikhail J. Atallah and Marina Blanton, editors, Algorithms and Theory of Computation Handbook, chapter Dynamic Graph Algorithms, pages 9.1{9.28. Chapman & Hall/CRC, 2010.

    6. Oded Green and David A. Bader. custinger: Supporting dynamic graph algorithms for gpus. 2016 IEEE High Performance Extreme Computing Conference (HPEC), pages 1{6, 2016.

    7. Monika R. Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM, 46(4):502{516, July 1999. URL:, doi:10.1145/320211.320215.

    8. Maurice Herlihy and Nir Shavit. On the Nature of Progress. In Principles of Distributed Systems - 15th International Conference, OPODIS 2011, Toulouse, France, December 13-16, 2011. Proceedings, pages 313{328, 2011. URL: http://dx. 22, doi:10.1007/978-3-642-25873-2_22.

    9. Maurice P. Herlihy and Jeannette M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463{492, 1990. doi:

    10. D. S. Hirschberg, A. K. Chandra, and D. V. Sarwate. Computing connected components on parallel computers. Commun. ACM, 22(8):461{464, August 1979. URL:, doi:10.1145/359138.359141.

  • Related Research Results (1)
  • Metrics
Share - Bookmark