-
August
| Su | Mo | Tu | We | Th | Fr | Sa |
|---|
| | | | | | 1 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| 23 | 24 | 25 | 26 | 27 | 28 | 29 |
| 30 | 31 | | | | | |
|
- Info
Voronoi diagrams, diameter and distance oracles for planar graphs
Wednesday, June 21st, 2017 16:10
Schreiber 309
Voronoi diagrams, diameter and distance oracles for planar graphs
Shay Mozes, IDC
Abstract:
Computing distances in graphs is a fundamental and important problem. In this talk I will survey some older and newer results concerning the computation of distances in planar graphs. I then plan to go into some of the details of efficiently constructing weighted Voronoi diagrams for planar graphs. I will also discuss two applications: computing the diameter in O(n^{5/3}) time, and exact distance oracles with O(n^{3/2}) space and O(log n) query time.
Based on joint works with Pawel Gawrychowski, Haim Kaplan, Micha Sharir, and Oren Weimann.
|
Forgot your password?