TY - GEN

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

AU - Chan, Timothy M.

AU - Skrepetos, Dimitrios

N1 - Publisher Copyright:
© Timothy M. Chan and Dimitrios Skrepetos.

PY - 2016/12/1

Y1 - 2016/12/1

N2 - 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.

AB - 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.

KW - All-pairs shortest paths

KW - Computational geometry

KW - Unit-disk graphs

UR - http://www.scopus.com/inward/record.url?scp=85010764229&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85010764229&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2016.24

DO - 10.4230/LIPIcs.ISAAC.2016.24

M3 - Conference contribution

AN - SCOPUS:85010764229

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 24.1-24.13

BT - 27th International Symposium on Algorithms and Computation, ISAAC 2016

A2 - Hong, Seok-Hee

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 27th International Symposium on Algorithms and Computation, ISAAC 2016

Y2 - 12 December 2016 through 14 December 2016

ER -