Fast Parallel Algorithm for Enumerating All Chordless Cycles in Graphs
Universidade Federal de Goias
arXiv:1410.4876 [cs.DC], (17 Oct 2014)
@article{2014arXiv1410.4876S,
author={Silva Dias}, E. and {Castonguay}, D. and {Longo}, H. and {Abdala Rfaei Jradi}, W. and {do Nascimento}, H.~A.~D.},
title={"{Fast Parallel Algorithm for Enumerating All Chordless Cycles in Graphs}"},
journal={ArXiv e-prints},
archivePrefix={"arXiv"},
eprint={1410.4876},
primaryClass={"cs.DC"},
keywords={Computer Science – Distributed, Parallel, and Cluster Computing},
year={2014},
month={oct},
adsurl={http://adsabs.harvard.edu/abs/2014arXiv1410.4876S},
adsnote={Provided by the SAO/NASA Astrophysics Data System}
}
Finding chordless cycles is an important theoretical problem in the Graph Theory area. It also can be applied to practical problems such as discover which predators compete for the same food in ecological networks. Motivated by the problem of theoretical interest and also by its significant practical importance, we present in this paper a parallel algorithm for enumerating all the chordless cycles in undirected graphs, which was implemented in OpenCL.
October 22, 2014 by hgpu
