References: [ Home | Author index | Key index | Search ]

RT2015

Rocha, Rodrigo and Thatte, Bhalchandra, Distributed cycle detection in large-scale sparse graphs.  October 2015.

Abstract: In this paper we present a distributed algorithm for detecting cycles in large-scale directed graphs, along with its correctness proof and analysis. The algorithm is then extended to find strong components in directed graphs. We indicate an application to detecting cycles in number theoretic functions such as the proper divisor function. Our prototype implementation of the cycle detection algorithm, when applied to the proper divisor function, detects all sociable groups of numbers (cycles in the proper divisor function) up to 10⁷.