Finding strongly connected components in distributed graphs |
| |
| Affiliation: | 1. University of Nevada – Reno, Reno, NV 89557, USA;2. University at Buffalo, The State University of New York, Buffalo, NY 14260, USA;1. Intelligent Systems Lab Amsterdam, University of Amsterdam, Science Park 904, 1098 XH, Amsterdam, Netherlands;2. Computer Vision Lab, Delft University of Technology, Delft, Netherlands |
| |
| Abstract: | The traditional, serial, algorithm for finding the strongly connected components in a graph is based on depth first search and has complexity which is linear in the size of the graph. Depth first search is difficult to parallelize, which creates a need for a different parallel algorithm for this problem. We describe the implementation of a recently proposed parallel algorithm that finds strongly connected components in distributed graphs, and discuss how it is used in a radiation transport solver. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
