A Comparative Study of Parallel Algorithms for the Girth Problem

Michael J. Dinneen, Masoud Khosravani, Kuai Wei
Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand
Tenth Australasian Symposium on Parallel and Distributed Computing (AusPDC 2012), 2012


   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},




Download Download (PDF)   View View   Source Source   



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.
Rating: 1.6/5. From 4 votes.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: