Space-efficient path-reporting approximate distance oracles

作者：Elkin Michael^*; Neiman Ofer; Wulff Nilsen Christian

来源：Theoretical Computer Science, 2016, 651: 1-10.

DOI：10.1016/j.tcs.2016.07.038

• Distance oracles
• Routing
• Labeling scheme

We consider approximate 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 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 (logn) words per vertex. The cost for such space efficiency is an increased stretch.

• 出版日期2016-10-25