Geodesic
The hierarchical hub labeling is non-efficient
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2015), pp. 44-47 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We study the shortest path problem in a graph using hub labeling. It is proved that a hierarchical hub labeling can be $\Omega(\sqrt n)$ times larger than the minimal (non-hierarchical) hub labeling. 
@article{VMUMM_2015_5_a8,
     author = {R. A. Savchenko},
     title = {The hierarchical hub labeling is non-efficient},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {44--47},
     year = {2015},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2015_5_a8/}
}
TY  - JOUR
AU  - R. A. Savchenko
TI  - The hierarchical hub labeling is non-efficient
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2015
SP  - 44
EP  - 47
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2015_5_a8/
LA  - ru
ID  - VMUMM_2015_5_a8
ER  - 
%0 Journal Article
%A R. A. Savchenko
%T The hierarchical hub labeling is non-efficient
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2015
%P 44-47
%N 5
%U http://geodesic.mathdoc.fr/item/VMUMM_2015_5_a8/
%G ru
%F VMUMM_2015_5_a8
R. A. Savchenko. The hierarchical hub labeling is non-efficient. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2015), pp. 44-47. http://geodesic.mathdoc.fr/item/VMUMM_2015_5_a8/

[1] Gavoille C., Peleg D., Pérennes S., Raz R., “Distance labeling in graphs”, J. Algorithms, 53:1 (2004), 85–112 | DOI | MR | Zbl

[2] Cohen E., Halperin E., Kaplan H., Zwick U., “Reachability and distance queries via 2-hop labels”, SIAM J. Comput., 32:5 (2003), 1338–1355 | DOI | MR | Zbl

[3] Abraham I., Delling D., Goldberg A.V., Werneck R.F., “Hierarchical hub labelings for shortest paths”, Algorithms, ESA 2012, Lect. Notes Comput. Sci., 7501, eds. L. Epstein, P. Ferragina, Springer, Heidelberg, 2012, 24–35 | DOI | MR | Zbl

[4] Akiba T., Iwata Y., Yoshida Y., “Fast exact shortest-path distance queries on large networks by pruned landmark labeling”, SIGMOD 13 Proc. 2013 ACM SIGMOD Int. Conf. on Management of Data, ACM, N.Y., 2013, 349–360

[5] Goldberg A.V., Razenshteyn I., Savchenko R., “Separating hierarchical and general hub labelings”, Mathematical Foundations of Computer Science 2013, Lect. Notes Comput. Sci., 8087, eds. K. Chatterjee, J. Sgall, Springer, Heidelberg, 2013, 469–479 | DOI | MR | Zbl

[6] Kormen T., Leizerson Ch., Rivest R., Algoritmy: postroenie i analiz, MTsNMO, M., 2000