Solving path problems on the GPU

DOI10.1016/J.PARCO.2009.12.002zbMATH Open1204.68043OpenAlexW2102067213MaRDI QIDQ991105FDOQ991105

Authors Aydin Buluç, J. R. Gilbert, 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

Gaussian eliminationgraph algorithmlinear algebrashortest pathmatrix multiplicationsemiringgraphical processing unitall-pairs shortest-paths

Mathematics Subject Classification ID

Computer system organization (68M99)

Recommendations

• Generalized blocked Floyd-Warshall algorithm
• Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures
• A blocked all-pairs shortest-paths algorithm
• scientific article; zbMATH DE number 1617277
• Solution of graph problems by means of the STAR-machine being implemented on GPUs

Cites work

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

Cited in

(10)

• Solving the examination timetabling problem in GPUs
• Route relaxations on GPU for vehicle routing problems
• Using GPU computing for solving the two-dimensional guillotine cutting problem
• Research and development of Johnson's algorithm parallel schemes in GPGPU technology
• Generalized blocked Floyd-Warshall algorithm
• Experiments-based parameter identification on the GPU for cooperative systems
• 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
• Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms
• ACL2 meets the GPU: formalizing a CUDA-based parallelizable all-pairs shortest path algorithm in ACL2

Describes a project that uses

Uses Software

• BLAS
• CUDA
• Boost
• BGL

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

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