1991/12/01 by Hillel Gazit · 2 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Graph Theory and Algorithms #Combinatorics #Randomized algorithm #Mathematics #Graph #Undirected graph #Binary logarithm #Algorithm #Freivalds' algorithm #Product (mathematics) #Running time #Discrete mathematics
paper · doi:10.1137/0220066
openalex publication_date 1991/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/04/04
A parallel randomized algorithm for finding the connected components of an undirected graph is presented. The algorithm has an expected running time of T = O(log (n)) with P = O((m + n) / log (n)) processors, where m is the number of edges and n is the number of vertices. The algorithm is optimal in the sense that the product P ⋅ T is a linear function of the input size. The algorithm requires O(m + n) space, which is the input size, so it is optimal in space as well.