Skip to Main content Skip to Navigation
New interface
Journal articles

Fast parallel algorithms for finding elementary circuits of a directed graph: a GPU-based approach

Abstract : Circuits in a graph are interesting structures and identifying them is of an important relevance for many applications. However, enumerating circuits is known to be a difficult problem, since their number can grow exponentially. In this paper, we propose fast parallel approaches for enumerating elementary circuits of directed graphs based on graphics processing unit (GPU). Our algorithms are based on a massive exploration of the graph in a breadth-first search strategy. Algorithm V-FEC explores the graph starting from different vertices simultaneously. To further reduce the search space, we present T-FEC, another algorithm that uses triplets as an initial set to start exploring. To the best of our knowledge, those are the first parallel GPU-based algorithms for finding all circuits of a given graph. In addition, they find circuits of a given length and circuits with a specific vertex or edge. The evaluation results show that the proposed approaches achieve up to 190x speed-up over Johnson’s algorithm, one of the most efficient sequential algorithms for finding circuits
Complete list of metadata

https://hal.laas.fr/hal-03793115
Contributor : Didier EL BAZ Connect in order to contact the contributor
Submitted on : Thursday, November 3, 2022 - 10:13:38 AM
Last modification on : Tuesday, November 22, 2022 - 1:58:15 PM

File

CIRCUIT.pdf
Files produced by the author(s)

Identifiers

Citation

Amira Benachour, Saïd Yahiaoui, Didier El Baz, Nadia Nouali-Taboudjemat, Hamamache Kheddouci. Fast parallel algorithms for finding elementary circuits of a directed graph: a GPU-based approach. Journal of Supercomputing, In press, ⟨10.1007/s11227-022-04835-3⟩. ⟨hal-03793115⟩

Share

Metrics

Record views

0

Files downloads

0