Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-constrained Cycles
 
research article

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-constrained Cycles

Blanusa, Jovan  
•
Atasu, Kubilay
•
Ienne, Paolo  
September 1, 2023
Acm Transactions On Parallel Computing

Cycles are one of the fundamental subgraph patterns and being able to enumerate them in graphs enables important applications in a wide variety of fields, including finance, biology, chemistry, and network science. However, to enable cycle enumeration in real-world applications, efficient parallel algorithms are required. In this work, we propose scalable parallelisation of state-of-the-art sequential algorithms for enumerating simple, temporal, and hop-constrained cycles. First, we focus on the simple cycle enumeration problem and parallelise the algorithms by Johnson and by Read and Tarjan in a fine-grained manner. We theoretically show that our resulting fine-grained parallel algorithms are scalable, with the fine-grained parallel ReadTarjan algorithm being strongly scalable. In contrast, we show that straightforward coarse-grained parallel versions of these simple cycle enumeration algorithms that exploit edge- or vertex-level parallelism are not scalable. Next, we adapt our fine-grained approach to enable the enumeration of cycles under time-window, temporal, and hop constraints. Our evaluation on a cluster with 256 CPU cores that can execute up to 1,024 simultaneous threads demonstrates a near-linear scalability of our fine-grained parallel algorithms when enumerating cycles under the aforementioned constraints. On the same cluster, our fine-grained parallel algorithms achieve, on average, one order of magnitude speedup compared to the respective coarse-grained parallel versions of the state-of-the-art algorithms for cycle enumeration. The performance gap between the fine-grained and the coarse-grained parallel algorithms increases as we use more CPU cores.

  • Details
  • Metrics
Type
research article
DOI
10.1145/3611642
Web of Science ID

WOS:001080454800002

Author(s)
Blanusa, Jovan  
Atasu, Kubilay
Ienne, Paolo  
Date Issued

2023-09-01

Publisher

Assoc Computing Machinery

Published in
Acm Transactions On Parallel Computing
Volume

10

Issue

3

Start page

15

Subjects

Technology

•

Cycle Enumeration

•

Parallel Graph Algorithms

•

Graph Pattern Mining

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LAP  
Available on Infoscience
February 16, 2024
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/203837
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés