Accelerating all-pairs shortest path algorithms for bipartite graphs on graphics processing units

Bipartite graphs are used to model and represent many real-world problems in biological and physical sciences. Finding shortest paths in bipartite graphs is an important task and has numerous applications. Different dynamic programming based solutions to find the shortest paths exists which differ on complexity and structure of graph. The computational complexity of these algorithms is a major concern. This work formulates the parallel versions of Floyd-Warshall and Torgasin-Zimmermann algorithms to compute the shortest paths in bipartite graphs efficiently. These algorithms are mapped to graphics processing unit using tropical matrix product. The performance for different realizations and parameters are compared for Floyd-Warshall and Torgasin-Zimmermann algorithms. Parallel implementation of Torgasin-Zimmermann algorithm attained a speed-up factor of almost 274 when compared with serial Floyd-Warshall algorithm for random-generated undirected graphs.

Automated summary

Bipartite graphs are commonly used in biological and physical sciences, and finding shortest paths in these graphs can be efficiently solved using dynamic programming algorithms. This study introduces parallel versions of Floyd-Warshall and Torgasin-Zimmermann algorithms, implemented on graphics processing unit using tropical matrix product. The performance of these algorithms is compared under different scenarios and parameters.