Record: No

Level: Graduate

Language: Chinese

Prerequisite

Discrete math.

Abstract

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.

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.

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, …

Lecturer Intro

蒋瀚如于2019年在中国科学技术大学取得计算机科学与技术博士学位，2019-2020年在鹏城实验室量子计算研究中心担任助理研究员，2020年加入BIMSA任助理研究员。他的主要研究方向为程序语言理论、编译器的形式化验证和量子计算中的程序语言问题。作为并发程序分离编译验证工作CASCompCert的主要完成人，获得程序语言领域顶级会议PLDI 2019的Distinguished Paper Award。

Lecturer Email: hanru@bimsa.cn

TA: Dr. Chuqi Cao, chuqicao@bimsa.cn