清华主页 EN
导航菜单

Graph algorithm

来源: 09-09

时间:15:20 - 16:55, Tue,Thu, 9/13/2022 - 12/8/2022

地点:Venue: 1118 Zoom: 242 742 6089 PW: BIMSA

主讲人: Hanru Jiang (Assistant Research Fellow)

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 2019Distinguished Paper Award


Lecturer Email: hanru@bimsa.cn

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


返回顶部
相关文章
  • Graph Theory

    Record: YesLevel: GraduateLanguage: EnglishPrerequisiteAbstractThe goal of this course is to give students an overview over the most fundamental concepts and results in modern graph theory.The topics which we plan to cover include: Basic notions: graphs, graph isomorphism, adjacency matrix, paths, cycles, connectivityTrees, spanning trees, Cayley's formula,Vertex and edge connectivity, 2-connec...

  • Rainbow structures, Latin squares & graph decompositions

    Abstract:A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs has a long history in discrete mathematics, going back to the 18th century work of Euler on Latin squares. Since then rainbow structures were the focus of extensive research and found numerous applications in design theory and graph decompositions. Many problem...