Geodesic
Using weighted graphs features for fast searching their parameters
Prikladnaâ diskretnaâ matematika, no. 2 (2012), pp. 95-99.

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

In this paper, some algorithms are presented for the fast search of center, radius and diameter of weighted graphs on all-pairs shortest path matrix, using features of real-world road networks graphs. They are compared with algorithms searching these parameters by simple pass through elements of matrix.
Keywords: graph center, graph radius, graph diameter, all-pairs shortest path matrix, graph features, weighted graph. 
@article{PDM_2012_2_a8,
     author = {A. R. Urakov and T. V. Timeryaev},
     title = {Using weighted graphs features for fast searching their parameters},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {95--99},
     publisher = {mathdoc},
     number = {2},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2012_2_a8/}
}
TY  - JOUR
AU  - A. R. Urakov
AU  - T. V. Timeryaev
TI  - Using weighted graphs features for fast searching their parameters
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2012
SP  - 95
EP  - 99
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2012_2_a8/
LA  - ru
ID  - PDM_2012_2_a8
ER  - 
%0 Journal Article
%A A. R. Urakov
%A T. V. Timeryaev
%T Using weighted graphs features for fast searching their parameters
%J Prikladnaâ diskretnaâ matematika
%D 2012
%P 95-99
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2012_2_a8/
%G ru
%F PDM_2012_2_a8
A. R. Urakov; T. V. Timeryaev. Using weighted graphs features for fast searching their parameters. Prikladnaâ diskretnaâ matematika, no. 2 (2012), pp. 95-99. http://geodesic.mathdoc.fr/item/PDM_2012_2_a8/

[1] Johnson D. B., “Efficient algorithms for shortest paths in sparse graph”, J. ACM, 24:1 (1977), 1–13 | DOI | MR | Zbl

[2] Galil Z., Margalit O., “All pairs shortest distances for graphs with small integer length edges”, Information and Computation, 134:2 (1977), 103–139 | DOI | MR

[3] Zwick U., Shoshan A., “All pairs shortest paths in undirected graphs with integer weights”, Proc. of the 40th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Washington, Washington, 1999, 605–614 | MR