Skip to content

Accelerating large graph algorithms on GPU using CUDA

· 0 citations · 24 references

TL;DR

This paper presents the parallelisation of three fundamental class of graph problem - Breadth First Search, Single Source Shortest Path, and All-Pair Shortest Path, using CUDA based implementation on GPUs and examines the performance of the algorithms on a diverse set of generated and procured large graphs.

View source

Similar papers

HP-MC: Quickly Computing Maximum Clique Sizes of Large Sparse Graphs

This work presents a novel algorithm named HP-MC that, like prior approaches, is based on the branch and bound search, but which outperforms the leading maximum clique codes on large sparse graphs of various topologies by up to 10x on average.

Cameron Bradley, M. Burtscher · 0 citations
Jul 2026

Efficient GPU-Accelerated Local Subgraph Counting

A high-performance GPU solution for local subgraph counting that preserves SCOPE's tree-decomposition framework while explicitly resolving the tension between massive GPU parallelism and limited device memory is developed.

Qiao He, Yi-Ran Li, Man-Lung Yiu et al. · 0 citations
Conference Sep 2026

Comparison of the Efficiency of Different Approaches to Accelerating the Algorithm for Enumerating Minimal Dominating Sets

The paper presents a comparative study of several implementations of the Magu algorithm for enumerating inclusion-minimal dominating sets in an undirected graph. Unlike the conventional approach, where parallelization is applied to a batch of independent computational runs, this work investigates internal parallelizati...

V. Kobak, Vitaly M. Porksheyan, Veronika V. Sukhanova · 0 citations
Open access Sep 2026

Scaling Up Density Decomposition on Massive Graphs

Density decomposition characterizes the multi-level dense structure of large networks and supports a wide range of graph mining applications. Given a graph G = (V, E) , it assigns each vertex an integral dense number (IDN) and produces a nested sequence of layers D 0 ⊇ D 1 ⊇ ... ⊇ D p that capture increasingl...

Ya-Long Zhang, Rong-Hua Li, Qi Zhang et al. · 0 citations
Conference Open access Sep 2026

Finding Simple Shortest-Paths via Centroids

Centroids are used to compute an arbitrary number of simple paths with some important benefits: the expansion of a single centroid delivers an arbitrary number of paths; only a single Dijk-stra search is required to complete the task; the same algorithm can be easily coupled with heuristics that improve search efficien...

Carlos Linares López, I. Herman · 0 citations
Preprint Aug 2026

A simple and practical $o(\sqrt{n})$-time algorithm for shortest paths in power law graphs

PBS is proposed and analyzed, a simple sublinear approximation algorithm for power-law graphs with parameter $\beta\in[2,3)$ that does not require any preprocessing, yet exhibits performance comparable to light index-based algorithms (of linear or sublinear index size).

Jiaqi Mao · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.