Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.24
URN: urn:nbn:de:0030-drops-67948
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6794/
Chan, Timothy M. ; Skrepetos, Dimitrios
All-Pairs Shortest Paths in Unit-Disk Graphs in Slightly Subquadratic Time
| pdf-format: |
|
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(n^2 log n) time, by running the O(n log n)-time single-source shortest path algorithm of Cabello and Jejcic [Comput. Geom., 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(n^2 sqrt{ frac{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.
BibTeX - Entry
@InProceedings{chan_et_al:LIPIcs:2016:6794,
author = {Timothy M. Chan and Dimitrios Skrepetos},
title = {{All-Pairs Shortest Paths in Unit-Disk Graphs in Slightly Subquadratic Time}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {24:1--24:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-026-2},
ISSN = {1868-8969},
year = {2016},
volume = {64},
editor = {Seok-Hee Hong},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6794},
URN = {urn:nbn:de:0030-drops-67948},
doi = {10.4230/LIPIcs.ISAAC.2016.24},
annote = {Keywords: unit-disk graphs, all-pairs shortest paths, computational geometry}
}
| Keywords: | unit-disk graphs, all-pairs shortest paths, computational geometry | |
| Seminar: | 27th International Symposium on Algorithms and Computation (ISAAC 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 07.12.2016 |
