2016/02/16 by Natcha Simsiri, Simsiri, Natcha, Kanat Tangwongsan +5
Computer Science · #Caching and Content Delivery #Cloud Computing and Resource Management #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Graph Theory and Algorithms #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1602.05232
openalex publication_date 2016/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
On an evolving graph that is continuously updated by a high-velocity stream of edges, how can one efficiently maintain if two vertices are connected? This is the connectivity problem, a fundamental and widely studied problem on graphs. We present the first shared-memory parallel algorithm for incremental graph connectivity that is both provably work-efficient and has polylogarithmic parallel depth. We also present a simpler algorithm with slightly worse theoretical properties, but which is easier to implement and has good practical performance. Our experiments show a throughput of hundreds of millions of edges per second on a 20-core machine.