A Comparative Study of Parallel Algorithms for the Girth Problem
Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand
Tenth Australasian Symposium on Parallel and Distributed Computing (AusPDC 2012), 2012
@article{dinneen2012comparative,
title={A Comparative Study of Parallel Algorithms for the Girth Problem},
author={Dinneen, M.J. and Khosravani, M. and Wei, K.},
journal={Parallel and Distributed Computing 2012},
pages={23},
year={2012}
}
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.
April 10, 2012 by hgpu
