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

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