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 Accéder directement au contenu
Article Dans Une Revue Journal of Supercomputing Année : 2023

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

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

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⟩
58 Consultations
88 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More