Open Online Lectures
Graph Classes and Dynamic Pogramming (INF 339)
A large number of interesting graph-theoretic problems are NP-hard. Nevertheless, many of these problems can be solved efficiently when restricted to classes of graphs obtained by bounding the magnitude of some structural parameter. In this series of lectures, we will be revisiting several of these structural parameters, as well as techniques to develop efficient (dynamic programming) algorithms for corresponding restrictions of NP-hard problems. In particular, we will be addressing several notions of decomposition, width measures, algorithmic meta-theorems and their connections to fields such as logic and automata theory.
Some specific topics to be addressed during the course are:
- Several notions of decompositions for graphs
- Dynamic programming algorithms for important NP-hard problems parameterized by width
- Connections with logic and automata theory
- Algorithmic metatheorems
The course will be self-contained. Therefore students with an interest in graph theory and algorithms are welcome.
Format of the Lectures
Each lecture will consist of a sequence of short videos , each covering a very specific subtopic. This format is similar to the format used in some mainstream E-learn platforms. The course will follow no specific book. Literature of relevance for the lectures will be provided as the course progresses.
Enrollment and Evaluation
Students at the University of Bergen will be able to formally enroll for the course, with the course code INF 339 (Selected Topics in Algorithms and Complexity). In this case, the grade will be Pass/Fail. The grade will be based on assignments and possibly on a final exam (to be determined). Upon completion of the course, the student will get 10 ECTS.