All-pairs shortest paths in unit-disk graphs in slightly subquadratic time

Timothy M. Chan, Dimitrios Skrepetos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we study the all-pairs shortest paths problem in (unweighted) unit-disk graphs. The previous best solution for this problem required O(n2 log n) time, by running the O (n log n)-time single-source shortest path algorithm of Cabello and Jejčič (2015) from every source vertex, where n is the number of vertices. We not only manage to eliminate the logarithmic factor, but also obtain the first (slightly) subquadratic algorithm for the problem, running in O(n2√log log n /log n) time. Our algorithm computes an implicit representation of all the shortest paths, and, in the same amount of time, can also compute the diameter of the graph.

Original languageEnglish (US)
Title of host publication27th International Symposium on Algorithms and Computation, ISAAC 2016
EditorsSeok-Hee Hong
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages24.1-24.13
ISBN (Electronic)9783959770262
DOIs
StatePublished - Dec 1 2016
Externally publishedYes
Event27th International Symposium on Algorithms and Computation, ISAAC 2016 - Sydney, Australia
Duration: Dec 12 2016Dec 14 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume64
ISSN (Print)1868-8969

Other

Other27th International Symposium on Algorithms and Computation, ISAAC 2016
Country/TerritoryAustralia
CitySydney
Period12/12/1612/14/16

Keywords

  • All-pairs shortest paths
  • Computational geometry
  • Unit-disk graphs

ASJC Scopus subject areas

  • Software

Cite this