Space-efficient path-reporting approximate distance oracles

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Space-efficient path-reporting approximate distance oracles. / Elkin, Michael; Neiman, Ofer; Wulff-Nilsen, Christian.

In: Theoretical Computer Science, Vol. 651, 2016, p. 1-10.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Elkin, M, Neiman, O & Wulff-Nilsen, C 2016, 'Space-efficient path-reporting approximate distance oracles', Theoretical Computer Science, vol. 651, pp. 1-10. https://doi.org/10.1016/j.tcs.2016.07.038

APA

Elkin, M., Neiman, O., & Wulff-Nilsen, C. (2016). Space-efficient path-reporting approximate distance oracles. Theoretical Computer Science, 651, 1-10. https://doi.org/10.1016/j.tcs.2016.07.038

Vancouver

Elkin M, Neiman O, Wulff-Nilsen C. Space-efficient path-reporting approximate distance oracles. Theoretical Computer Science. 2016;651:1-10. https://doi.org/10.1016/j.tcs.2016.07.038

Author

Elkin, Michael ; Neiman, Ofer ; Wulff-Nilsen, Christian. / Space-efficient path-reporting approximate distance oracles. In: Theoretical Computer Science. 2016 ; Vol. 651. pp. 1-10.

Bibtex

@article{f48f9953318f48e6bd568812bfcfc643,
title = "Space-efficient path-reporting approximate distance oracles",
abstract = "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 nlog⁡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(log⁡n) words per vertex. The cost for such space efficiency is an increased stretch.",
keywords = "Distance oracles, Labeling scheme, Routing",
author = "Michael Elkin and Ofer Neiman and Christian Wulff-Nilsen",
year = "2016",
doi = "10.1016/j.tcs.2016.07.038",
language = "English",
volume = "651",
pages = "1--10",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Space-efficient path-reporting approximate distance oracles

AU - Elkin, Michael

AU - Neiman, Ofer

AU - Wulff-Nilsen, Christian

PY - 2016

Y1 - 2016

N2 - 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 nlog⁡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(log⁡n) words per vertex. The cost for such space efficiency is an increased stretch.

AB - 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 nlog⁡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(log⁡n) words per vertex. The cost for such space efficiency is an increased stretch.

KW - Distance oracles

KW - Labeling scheme

KW - Routing

U2 - 10.1016/j.tcs.2016.07.038

DO - 10.1016/j.tcs.2016.07.038

M3 - Journal article

AN - SCOPUS:84991401930

VL - 651

SP - 1

EP - 10

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

ID: 168286103