Options
Accelerating all-pairs shortest path algorithms for bipartite graphs on graphics processing units
Publikationstyp
Journal Article
Publikationsdatum
2022-02-09
Sprache
English
Institut
Enthalten in
Volume
81
Issue
7
Start Page
9549
End Page
9566
Citation
Multimedia Tools and Applications 81 (7): 9549-9566 (2022-03-01)
Publisher DOI
Scopus ID
2-s2.0-85124519071
Publisher
Springer Science + Business Media B.V
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.
Schlagworte
Bipartite graphs
CUDA
Graphics processing unit
Graphs
Parallelization
Shortest path
DDC Class
004: Informatik
510: Mathematik