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

Timothy M. Chan; Dimitrios Skrepetos

doi:10.4230/LIPIcs.ISAAC.2016.24

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

Research output: Chapter in Book/Report/Conference proceeding › Conference 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(n² 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(n²√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 language	English (US)
Title of host publication	27th International Symposium on Algorithms and Computation, ISAAC 2016
Editors	Seok-Hee Hong
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	24.1-24.13
ISBN (Electronic)	9783959770262
DOIs	https://doi.org/10.4230/LIPIcs.ISAAC.2016.24
State	Published - Dec 1 2016
Externally published	Yes
Event	27th International Symposium on Algorithms and Computation, ISAAC 2016 - Sydney, Australia Duration: Dec 12 2016 → Dec 14 2016

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	64
ISSN (Print)	1868-8969

Other

Other	27th International Symposium on Algorithms and Computation, ISAAC 2016
Country/Territory	Australia
City	Sydney
Period	12/12/16 → 12/14/16

Keywords

All-pairs shortest paths
Computational geometry
Unit-disk graphs

ASJC Scopus subject areas

Software

Online availability

10.4230/LIPIcs.ISAAC.2016.24

Library availability

Discover UIUC Full Text

Cite this

Chan, T. M., & Skrepetos, D. (2016). All-pairs shortest paths in unit-disk graphs in slightly subquadratic time. In S.-H. Hong (Ed.), 27th International Symposium on Algorithms and Computation, ISAAC 2016 (pp. 24.1-24.13). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 64). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2016.24

All-pairs shortest paths in unit-disk graphs in slightly subquadratic time. / Chan, Timothy M.; Skrepetos, Dimitrios.
27th International Symposium on Algorithms and Computation, ISAAC 2016. ed. / Seok-Hee Hong. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. p. 24.1-24.13 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 64).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chan, TM & Skrepetos, D 2016, All-pairs shortest paths in unit-disk graphs in slightly subquadratic time. in S-H Hong (ed.), 27th International Symposium on Algorithms and Computation, ISAAC 2016. Leibniz International Proceedings in Informatics, LIPIcs, vol. 64, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 24.1-24.13, 27th International Symposium on Algorithms and Computation, ISAAC 2016, Sydney, Australia, 12/12/16. https://doi.org/10.4230/LIPIcs.ISAAC.2016.24

Chan TM, Skrepetos D. All-pairs shortest paths in unit-disk graphs in slightly subquadratic time. In Hong SH, editor, 27th International Symposium on Algorithms and Computation, ISAAC 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2016. p. 24.1-24.13. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.ISAAC.2016.24

Chan, Timothy M. ; Skrepetos, Dimitrios. / All-pairs shortest paths in unit-disk graphs in slightly subquadratic time. 27th International Symposium on Algorithms and Computation, ISAAC 2016. editor / Seok-Hee Hong. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. pp. 24.1-24.13 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{1a503af88405409592c3ed4b6c676b14,

title = "All-pairs shortest paths in unit-disk graphs in slightly subquadratic time",

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{\v c}i{\v c} (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.",

keywords = "All-pairs shortest paths, Computational geometry, Unit-disk graphs",

author = "Chan, {Timothy M.} and Dimitrios Skrepetos",

note = "Publisher Copyright: {\textcopyright} Timothy M. Chan and Dimitrios Skrepetos.; 27th International Symposium on Algorithms and Computation, ISAAC 2016 ; Conference date: 12-12-2016 Through 14-12-2016",

year = "2016",

month = dec,

day = "1",

doi = "10.4230/LIPIcs.ISAAC.2016.24",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "24.1--24.13",

editor = "Seok-Hee Hong",

booktitle = "27th International Symposium on Algorithms and Computation, ISAAC 2016",

}

TY - GEN

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

AU - Chan, Timothy M.

AU - Skrepetos, Dimitrios

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 -

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

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this