Geodesic
All-pairs shortest paths algorithm for high-dimensional sparse graphs
Prikladnaâ diskretnaâ matematika, no. 1 (2013), pp. 84-92

Voir la notice de l'article provenant de la source Math-Net.Ru

All-pairs shortest path problem on weighted undirected sparse graphs is considered. “Disassembly and assembly of graph” algorithm is proposed to obtain the solution of the problem for the given graph using the solution of the problem for a small-dimensional graph. The algorithm is compared with one of the fastest classic algorithms on public source data.
Mots-clés : APSP
Keywords: graph disassembly, graph assembly, sparse graphs. 
@article{PDM_2013_1_a6,
     author = {A. R. Urakov and T. V. Timeryaev},
     title = {All-pairs shortest paths algorithm for high-dimensional sparse graphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {84--92},
     publisher = {mathdoc},
     number = {1},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_1_a6/}
}
TY  - JOUR
AU  - A. R. Urakov
AU  - T. V. Timeryaev
TI  - All-pairs shortest paths algorithm for high-dimensional sparse graphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 84
EP  - 92
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_1_a6/
LA  - ru
ID  - PDM_2013_1_a6
ER  - 
%0 Journal Article
%A A. R. Urakov
%A T. V. Timeryaev
%T All-pairs shortest paths algorithm for high-dimensional sparse graphs
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 84-92
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2013_1_a6/
%G ru
%F PDM_2013_1_a6
A. R. Urakov; T. V. Timeryaev. All-pairs shortest paths algorithm for high-dimensional sparse graphs. Prikladnaâ diskretnaâ matematika, no. 1 (2013), pp. 84-92. http://geodesic.mathdoc.fr/item/PDM_2013_1_a6/