Title: Space-Efficient Path-Reporting Approximate Distance Oracles.

Authors: Michael Elkin, Ofer Neiman and Christian Wulff-Nilsen.

Abstract: We consider approximate {\em path-reporting} distance oracles, distance labeling and labeled routing with extremely low space requirements, for general undirected graphs. For distance oracles, we show how to break the $n\log n$ space
bound of Thorup and Zwick if approximate {\em paths} rather than distances need to be reported.
For approximate distance labeling and labeled routing,
we break the previously best known space bound of $O(\log n)$ words per vertex.
 The cost for such space efficiency is an increased stretch.