Options
An all-pairs shortest path algorithm for bipartite graphs
Citation Link: https://doi.org/10.15480/882.15551
Publikationstyp
Journal Article
Date Issued
2013-12-01
Sprache
English
TORE-DOI
Journal
Volume
3
Issue
4
Start Page
149
End Page
157
Citation
Open computer science 3 (4): 149-157 (2013)
Publisher DOI
Publisher
Versita
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.
Subjects
bipartite graph
tropical (min-plus) algebra
shortest path
distance matrix product
DDC Class
510: Mathematics
Publication version
publishedVersion
Loading...
Name
10.2478_s13537-013-0110-4.pdf
Type
Main Article
Size
379.31 KB
Format
Adobe PDF