An Adaptive Parallel Algorithm for Computing Connected Components

Chirag Jain, Patrick Flick, Tony Pan +2

We present an efficient distributed memory parallel algorithm for computing connected components in undirected graphs based on Shiloach-Vishkin's PRAM approach. We discuss multiple…