External GPU Biconnected Components

doi:10.1007/978-3-031-99872-0_10

External GPU Biconnected Components

2026-01-01

0

PRE

AI

S

Sahu, Abhijeet *

A

Andaluri S. P. V. M. Aditya

DOI：10.1007/978-3-031-99872-0_10

Original

Original request for help

Save

Abstract

En 中文

As the scale of graph analytics continues to grow, many applications require identifying biconnected components (bccs) and cut vertices in graphs that exceed the memory capacity of a single gpu. This paper presents an out-of-core, gpu-based batch processing algorithm designed to efficiently compute bccs and cut vertices in massive graphs that do not fit entirely into device memory. We propose a novel batch technique to process the graph incrementally, and maintain a Biconnectivity Compressed Graph to compute bccs and cut vertices. Experimental results on a range of large-scale benchmark graphs demonstrate that our technique achieves competitive performance compared to state-of-the-art cpu solutions, enabling the handling of graph instances previously considered intractable on gpu platforms.

Keywords:

Large-scale graphs

Biconnected components

Articulation points

Cut vertices

Out-of-core processing

GPU

Batch processing

External GPU Biconnected Components

Abstract

Journal

Organization