Parallel graph component labelling with GPUs and CUDA

DOI10.1016/J.PARCO.2010.07.002MaRDI QIDQ608854zbMATH OpenOpenAlexWikidataFDO

Authors K. A. Hawick, A. Leist, D. P. Playne

Publication date 26 November 2010

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.parco.2010.07.002

zbMATH Keywords

CUDAdata-parallel algorithmsGPUgraph component labellingmesh

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computer system organization (68M99) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Graph coloring using GPUs
• Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components
• Solution of graph problems by means of the STAR-machine being implemented on GPUs
• Utilization of OpenCL for large graph problems on graphics processing unit
• Parallel graduated assignment algorithm for multiple graph matching based on a common labelling

Cites work

• Collective dynamics of `small-world' networks
• Emergence of Scaling in Random Networks
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 42739 (Why is no real title available?)
• scientific article; zbMATH DE number 41029 (Why is no real title available?)
• scientific article; zbMATH DE number 1863545 (Why is no real title available?)
• Introduction to algorithms
• New methods to color the vertices of a graph
• The structure of scientific collaboration networks

Cited in

(10)

• Cropped quad-tree based solid object colouring with CUDA
• Antimagicness of generalized corona and snowflake graphs
• Graph coloring using GPUs
• Time-stepping methods for the simulation of the self-assembly of nano-crystals in MATLAB on a GPU
• GPU-based single-cluster algorithm for the simulation of the Ising model
• Finite-size scaling in ferromagnetic spin systems on the pyrochlore lattice
• Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components
• Graph coarsening and clustering on the GPU
• Parametric multi-step scheme for GPU-accelerated graph decomposition into strongly connected components
• Entanglement entropy from non-equilibrium Monte Carlo simulations

Describes a project that uses

Uses Software

• CUDA

This page was built for publication: Parallel graph component labelling with GPUs and CUDA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q608854)