Contents: Description, Announcements, Organization, Course Outline, Papers to Present, Lectures
Shortest path algorithms are widely used, for example in network routing, map navigation, motion planning, network analysis, and so on.
This course will begin with classical algorithms for shortest paths in graphs and geometric settings. We will then study improvements and variations (k-th shortest paths, dynamic graphs, link distance in polygons, approximate shortest paths in 3D, etc.). Finally, we will turn to related topics, including spanners, network routing, touring, and shortest paths in implicit graphs, including reconfiguration problems.
Time and Place: MW, 9:00 -- 10:20. Room DC 2568.
Credit:
Due | ||
Assignment 1 [pdf] | Monday Sep. 29 | |
Assignment 2 [pdf] | later |
Topics:
L01 | M Sep 8 | class-notes |
Introduction to the course. Review of Dijkstra's algorithm. Write a mini-review of Dijkstra's paper (see Piazza for instructions). Due by September 15. |
L02 | W Sep 10 | class-notes |
Shortest paths in a polygon / polygonal domain. |
L03 | M Sep 15 | class-notes | Shortest paths in polygonal domain (continued). Outline of further topics in geometric shortest paths. |
L04 | W Sep 17 | class-notes | More geometric shortest paths papers to present. Basic graph shortest path algorithms. |
L05 | M Sep 22 | class-notes | More basic graph shortest path algorithms. Papers to present. |
L06 | M Sep 24 | (no notes) class-notes |
Presentation by A. Linhares on "Computing the shortest path: A* search meets graph theory". Papers to present on spanners. |
L07 | M Sep 29 | class-notes | Lecture by Timothy Chan on all-pairs shortest path algorithms. |
L08 | W Oct 1 | class-notes | Chen and Han's algorithm for shortest paths on polyhedra surfaces. |
L09 | M Oct 6 | class-notes | Travelling Salesman Problem. Touring a sequence of polygons. Papers on routing. |
L10 | W Oct 8 | (no notes) class-notes |
Presentation by H. Vosoughpour on "Computing Shortest Paths among Curved Obstacles in the Plane". Shortest descending paths. |
L11 | W Oct 15 | (no notes) | Lecture by Mustaq Ahmed, Google, on: (1) shortest paths with forbidden subgraphs; (2) Google Ground Truth. |
L12 | M Oct 20 |
Presentation by P. Demontigny: Randomized Speedup of the Bellman-Ford Algorithm.
Presentation by N. Lindzey: Finding the k shortest paths. | |
L13 | W Oct 22 |
Presentation by K. Ammar: A new approach to dynamic all pairs shortest paths
Presentation by A. Domurad: Resource constrained shortest paths. | |
L14 | M Oct 27 |
Presentation by O. Grant: \ frac {13}{9}-Approximation for Graphic TSP
Presentation by S. Pratt: Competitive routing in the half-θ 6-graph | |
L15 | W Oct 29 | class-notes |
Presentation by S. Chowdhury A simple shortest path algorithm with linear average time
Frechet distance. |
L16 | M Nov 3 |
Presentation by R. Goldade: Fast exact and approximate geodesics on meshes
Presentation by A. Lubiw: Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication) | |
L17 | W Nov 5 |
Presentation by Z. Peng: Routing with guaranteed delivery in ad hoc wireless networks
Presentation by P. Goel: Combining speed-up techniques for shortest-path computations | |
L18 | M Nov 10 |
Presentation by S. Lee: On the all-pairs-shortest-path problem in unweighted undirected graphs
Open Problems | |
L19 | W Nov 12 | class-notes |
Presentation by V. Subramanya: Planar graphs, negative weight edges, shortest paths, and near linear time
self-approaching paths |
L20 | M Nov 17 |
Presentation by S. Aflaki: Matrix searching with the shortest-path metric
Presentation by J. Liu: AnO (n logn) algorithm for computing the link center of a simple polygon | |
L21 | W Nov 19 | Lecture by V. Pathak on reconfiguration problems | |
L22 | M Nov 24 |
Presentation by J. Jung:
Presentation by J. Wang: Succinct greedy drawings do not always exist | |
L23 | W Nov 26 |
Presentation by V. Menon: Faster algorithms for the shortest path problem
Presentation by D. Skrepetos: | |
L24 | M Dec 1 |
Academic Integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility.
[Check www.uwaterloo.ca/academicintegrity for more information. ]
Grievance: A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70 - Student Petitions and Grievances, Section 4. When in doubt please be certain to contact the department's administrative assistant who will provide further assistance.
Note for students with disabilities: The Office for Persons with Disabilities (OPD), located in Needles Hall, Room 1132, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with the OPD at the beginning of each academic term.