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.

UDC: 519.178

Received: 28.04.2014

 English version: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2015, 70:5, 223–225

Bibliographic databases:

• 
• 
•