Fast parallel algorithms for finding elementary circuits of a directed graph: a GPU-based approach - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Access content directly
Journal Articles Journal of Supercomputing Year : 2023

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
Fichier principal
Vignette du fichier
CIRCUIT.pdf (592.77 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03793115 , version 1 (03-11-2022)

Identifiers

Cite

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, 2023, 79 (5), pp.4791-4819. ⟨10.1007/s11227-022-04835-3⟩. ⟨hal-03793115⟩
20 View
4 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More