Shortest paths algorithms 1000-2M24ANS
1. Variants of the problem and models of computation. Basic algorithms: Dijkstra, Bellman-Ford, their generalizations, weight scaling.
2. Classical scaling algorithms for single-source shortest paths (SSSP) with negative weights: Goldberg, Gabow-Tarjan.
3. Conditional lower bounds: equivalence of all-pairs shortest paths (APSP), negative triangle detection, and related problems.
4. Dynamic data structures maintaining shortest paths (a selection).
5. Algebraic algorithms: APSP in directed and undirected graphs; distance oracles.
6. Spanners. Approximate distance oracles in undirected graphs.
7. Low-diameter decomposition (LDD) in undirected and directed graphs and applications.
8. SSSP with negative weights in almost linear time.
9. Parallel algorithms: the classical, reducing exact integer SSSP to an approximate variant, parallel LDD.
10. Basic techniques for planar and minor-free graphs.
11. Shortest paths in real-life graphs: highway dimension.
Type of course
Prerequisites
Prerequisites (description)
Course coordinators
Learning outcomes
Knowledge: the student:
1. knows and can motivate the most important settings which fundamental path problems in graphs are studied in,
2. understands the importance of model of computation's choice for determining the computational complexity of algorithmic problems,
3. has advanced knowledge on designing algorithms solving (polynomial) graph problems and proving their (conditional) lower bounds.
Skills: the student:
1. can apply the learned techniques to construct efficient algorithms for graph problems or to prove their hardness,
2. can formally prove the correctness and determine the time complexity of algorithms in the studied settings: static, dynamic, and parallel.
Competences: the student:
1. knows the limitations of their own knowledge and the need of further study, and in particular the necessity of obtaining knowledge from outside the field,
2. the student understands the need to systematically read scientific articles to broaden and expand his/her knowledge.
Assessment criteria
The final grade will depend on the results of the homeworks (theoretical; about 70%) and the oral exam (about 30%).
The oral exam will be in one of two forms (to be chosen by each student):
1. a test of knowledge of the lecture material covered, or
2. a discussion about a single related scientific article not covered in class, to be read independently by the student. A list of possible articles will be provided. It is allowed to choose an article from outside the list, but such an article will have to be approved be the lecturer beforehand.
In the case of doctoral students, only the second form of oral examination is allowed.
Bibliography
Notes and research articles provided or indicated by the lecturer.
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: