2025/08/15 by Torgasin, Svetlana, Zimmermann, Karl-Heinz
#Natural Sciences and Mathematics::510: Mathematics #bipartite graph #distance matrix product #shortest path #tropical (min-plus) algebra
paper · doi:10.15480/882.15551
Abstract Bipartite graphs are widely used for modeling of complex structures in biology, engineering, and computer science. The search for shortest paths in such structures is a highly demanded procedure that requires optimization. This paper presents a variant of the all-pairs shortest path algorithm for bipartite graphs. The method is based on the distance matrix product and improves the general algorithm by exploiting the graph topology. The space complexity is reduced by a factor of at least four and the time complexity decreased by almost an order of magnitude when compared with the basic APSP algorithm.