期刊
MULTIMEDIA TOOLS AND APPLICATIONS
卷 81, 期 7, 页码 9549-9566出版社
SPRINGER
DOI: 10.1007/s11042-022-12066-0
关键词
Shortest path; Graphs; Bipartite graphs; Graphics processing unit; CUDA; Parallelization
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.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据