Graph Algorithm
In this course, we introduce basic concepts in graph theory and complexity theory, then study graph algorithms with a focus on matching and network flows.
Lecturer
Date
13th September ~ 29th December, 2022
Website
Prerequisite
Discrete math.
Syllabus
(Tentative)
- Foundamental concepts: graphs, paths, walks, cycles, trees, isomorphism, adjacency matrix, complexity classes, reduction, completeness, …
- Matching: bipartite maximum matching, bipartite minimum-cost perfect matching, Primal-dual min-cost matching, online maching…
- Flow: max-flow min-cut theorem, Ford-Fulkerson and Edmonds-Karp algorithms, Dinitz's algorithm, Hopcroft-Karp algorithm, Menger's theorem…
- NP-complete problems: max-cut, independent set, …
- Approximate algorithms: vertex cover, max-cut, graph coloring, …
- Spectural graph theory: Courant-Fischer theorem, graph Laplacian, Cheeger's inequality, graph sparsification, …
- Foundamental concepts: graphs, paths, walks, cycles, trees, isomorphism, adjacency matrix, complexity classes, reduction, completeness, …
- Matching: bipartite maximum matching, bipartite minimum-cost perfect matching, Primal-dual min-cost matching, online maching…
- Flow: max-flow min-cut theorem, Ford-Fulkerson and Edmonds-Karp algorithms, Dinitz's algorithm, Hopcroft-Karp algorithm, Menger's theorem…
- NP-complete problems: max-cut, independent set, …
- Approximate algorithms: vertex cover, max-cut, graph coloring, …
- Spectural graph theory: Courant-Fischer theorem, graph Laplacian, Cheeger's inequality, graph sparsification, …
Reference
1. Introduction to Graph Theory, by Douglas B. West.
2. Modern Graph Theory, by Bela Bollobas.
3. The Design and Analysis of Algorithms, by Dexter Kozen.
2. Modern Graph Theory, by Bela Bollobas.
3. The Design and Analysis of Algorithms, by Dexter Kozen.
Audience
Graduate
Video Public
No
Notes Public
No
Language
Chinese
Lecturer Intro
Hanru Jiang obtained a Ph.D. in computer science and technology from the University of Science and Technology of China in 2019. From 2019 to 2020, he worked as an assistant research fellow at the Quantum Computing Research Center of Pengcheng Laboratory. In 2020, he joined BIMSA as an assistant professor. His main research directions are programming language theory, compiler verification, and programming language aspects in quantum computing. As the main contributor to the concurrent program separation compilation verification work CASCompCert, won the Distinguished Paper Award of PLDI 2019, a top conference in the field of programming languages.