|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2015, Number 5, Pages 44–47
(Mi vmumm267)
|
|
|
|
Short notes
The hierarchical hub labeling is non-efficient
R. A. Savchenko Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
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.
Key words:
find shortest path in a graph, hub labeling, hierarchical hub labeling.
Received: 28.04.2014
Citation:
R. A. Savchenko, “The hierarchical hub labeling is non-efficient”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2015, no. 5, 44–47; Moscow University Mathematics Bulletin, 70:5 (2015), 223–225
Linking options:
https://www.mathnet.ru/eng/vmumm267 https://www.mathnet.ru/eng/vmumm/y2015/i5/p44
|
Statistics & downloads: |
Abstract page: | 86 | Full-text PDF : | 21 | References: | 22 |
|