Rights Creative Commons: Attribution 3.0 Hong Kong License Improved Parallel Algorithms for Finding Connected Components

Finding the connected components of a graph is a basic computational problem. In recent years, there were several exciting results in breaking the log ’ n-time barrier to finding connected components on parallel machines using shared memory without concurrent-write capability. This paper further presents two new parallel algorithms both using less than log2 7 ~ time. The merit of the first algo-rithm is that it uses only a sublinear number of processors, yet retains the time complexity of the fastest existing algorithm. The second algorithm is slightly slower but its work (i.e., the time-processor product) is closer to op-timal than all previous algorithms using less than log’n time.