License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.55
URN: urn:nbn:de:0030-drops-63354
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6335/
Go to the corresponding LIPIcs Volume Portal

Sommer, Christian

All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing

pdf-format:
LIPIcs-ICALP-2016-55.pdf (0.5 MB)

Abstract

Given an undirected, unweighted graph G on n nodes, there is an O(n^2*poly log(n))-time algorithm that computes a data structure called distance oracle of size O(n^{5/3}*poly log(n)) answering approximate distance queries in constant time. For nodes at distance d the distance estimate is between d and 2d + 1.

This new distance oracle improves upon the oracles of Patrascu and Roditty (FOCS 2010), Abraham and Gavoille (DISC 2011), and Agarwal and Brighten Godfrey (PODC 2013) in terms of preprocessing time, and upon the oracle of Baswana and Sen (SODA 2004) in terms of stretch. The running time analysis is tight (up to logarithmic factors) due to a recent lower bound of Abboud and Bodwin (STOC 2016).

Techniques include dominating sets, sampling, balls, and spanners, and the main contribution lies in the way these techniques are combined. Perhaps the most interesting aspect from a technical point of view is the application of a spanner without incurring its constant additive stretch penalty.

BibTeX - Entry

@InProceedings{sommer:LIPIcs:2016:6335,
  author =	{Christian Sommer},
  title =	{{All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6335},
  URN =		{urn:nbn:de:0030-drops-63354},
  doi =		{10.4230/LIPIcs.ICALP.2016.55},
  annote =	{Keywords: graph algorithms, data structures, approximate shortest paths, distance oracles, distance labels}
}

Keywords: graph algorithms, data structures, approximate shortest paths, distance oracles, distance labels
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI