A Comparative Study of Parallel Algorithms for the Girth Problem

Dinneen, M. J., Khosravani, M. and Wei, K.

In this paper we introduce efficient parallel algorithms for finding the girth in a graph or digraph, where girth is the length of a shortest cycle. We empirically compare our algorithms by using two common APIs for parallel programming in C++, which are OpenMP for multiple CPUs and CUDA for multi-core GPUs. We conclude that both hardware platforms and programming models have their benefits.

Cite as: Dinneen, M. J., Khosravani, M. and Wei, K. (2012). A Comparative Study of Parallel Algorithms for the Girth Problem. In Proc. Australasian Symposium on Parallel and Distributed Computing (AusPDC 2012) Melbourne, Australia. CRPIT, 127. Chen, J. and Ranjan, R. Eds., ACS. 23-30

(from crpit.com) (local if available)