An all-pairs shortest path algorithm for bipartite graphs
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.
- Location
-
Deutsche Nationalbibliothek Frankfurt am Main
- Extent
-
Online-Ressource
- Language
-
Englisch
- Bibliographic citation
-
An all-pairs shortest path algorithm for bipartite graphs ; volume:3 ; number:4 ; year:2013 ; pages:149-157 ; extent:9
Open computer science ; 3, Heft 4 (2013), 149-157 (gesamt 9)
- Creator
-
Torgasin, Svetlana
Zimmermann, Karl-Heinz
- DOI
-
10.2478/s13537-013-0110-4
- URN
-
urn:nbn:de:101:1-2410301513016.039216862102
- Rights
-
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Last update
-
15.08.2025, 7:28 AM CEST
Data provider
This object is provided by:
Deutsche Nationalbibliothek. If you have any questions about the object, please contact the data provider.
Deutsche Nationalbibliothek. If you have any questions about the object, please contact the data provider.
Associated
- Torgasin, Svetlana
- Zimmermann, Karl-Heinz
Other Objects (12)
Computing shortest path distances based on cluster-pairs
Acceleration of Shortest Path and Constrained Shortest Path Computation
Shortest path problem using Bellman algorithm under neutrosophic environment
A Fast Shortest Path Algorithm on Terrain-like Graphs
Shortest path network problems
Distributed shortest-path computation
New Multiobjective Shortest Path Algorithms
Recoverable Robust Shortest Path Problems
Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem
Dijkstra algorithm for shortest path problem under interval-valued Pythagorean fuzzy environment
A dynamic programming algorithm for solving the k-Color Shortest Path Problem
Variants of the Shortest Path Problem
Computing shortest path distances based on cluster-pairs
Acceleration of Shortest Path and Constrained Shortest Path Computation
Shortest path problem using Bellman algorithm under neutrosophic environment
A Fast Shortest Path Algorithm on Terrain-like Graphs
Shortest path network problems
Distributed shortest-path computation
New Multiobjective Shortest Path Algorithms
Recoverable Robust Shortest Path Problems
Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem
Dijkstra algorithm for shortest path problem under interval-valued Pythagorean fuzzy environment
A dynamic programming algorithm for solving the k-Color Shortest Path Problem
Variants of the Shortest Path Problem
Computing shortest path distances based on cluster-pairs
Acceleration of Shortest Path and Constrained Shortest Path Computation
Shortest path problem using Bellman algorithm under neutrosophic environment
A Fast Shortest Path Algorithm on Terrain-like Graphs
Shortest path network problems
Distributed shortest-path computation
New Multiobjective Shortest Path Algorithms
Recoverable Robust Shortest Path Problems
Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem
Dijkstra algorithm for shortest path problem under interval-valued Pythagorean fuzzy environment
A dynamic programming algorithm for solving the k-Color Shortest Path Problem