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

Simple item page
dc.contributor.authorBenachour, Amira
dc.contributor.authorYahiaoui, Saïd
dc.contributor.authorEl Baz, Didier
dc.contributor.authorNouali‑Taboudjemat, Nadia
dc.contributor.authorKheddouci, Hamamache
dc.date.accessioned2023-02-26T10:27:46Z
dc.date.available2023-02-26T10:27:46Z
dc.date.issued2023-03
dc.description.abstractCircuits 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.
dc.identifier.issn1573-0484
dc.identifier.urihttps://dl.cerist.dz/handle/CERIST/969
dc.publisherSpringer Science+Business Media
dc.relation.ispartofseriesThe Journal of Supercomputing : An International Journal of High-Performance Computer Design, Analysis, and Use; Vol. 79 - N° 5
dc.relation.pages0920-8542
dc.structureCalcul pervasif et mobile (Pervasive and Mobile Computing group)
dc.subjectFinding circuits
dc.subjectCycles
dc.subjectDirected graph
dc.subjectParallel processing
dc.subjectGPU
dc.titleFast parallel algorithms for finding elementary circuits of a directed graph: a GPU-based approach
dc.typeArticle
Files
Collections
International Journal Papers