Solving path problems on the GPU

DOI10.1016/j.parco.2009.12.002zbMath1204.68043OpenAlexW2102067213MaRDI QIDQ991105

John R. Gilbert, Aydın Buluç, Ceren Budak

Publication date: 2 September 2010

Published in: Parallel Computing (Search for Journal in Brave)

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

zbMATH Keywords

shortest pathgraph algorithmGaussian eliminationlinear algebrasemiringmatrix multiplicationgraphical processing unitall-pairs shortest-paths

Mathematics Subject Classification ID

Computer system organization (68M99)

Related Items (5)

Utilization of OpenCL for large graph problems on graphics processing unit ⋮ Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms ⋮ Route relaxations on GPU for vehicle routing problems ⋮ Experiments-based parameter identification on the GPU for cooperative systems ⋮ Using GPU Computing for Solving the Two-Dimensional Guillotine Cutting Problem

Uses Software

• BLAS
• CUDA
• Boost
• BGL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• R-Kleene: a high-performance divide-and-conquer algorithm for the all-pair shortest path for densely connected networks
• Matrix multiplication via arithmetic progressions
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• The input/output complexity of transitive closure
• Gaussian elimination is not optimal
• Cache-oblivious dynamic programming
• A Unified Approach to Path Problems
• Efficient Algorithms for Shortest Paths in Sparse Networks
• A set of level 3 basic linear algebra subprograms
• Locality of Reference in LU Decomposition with Partial Pivoting
• Recursive Blocked Algorithms and Hybrid Data Structures for Dense Matrix Library Software

This page was built for publication: Solving path problems on the GPU