NOC:Advanced Graph Theory


Lecture 1 - Graph Theory: Introduction


Lecture 2 - Paths, Cycles and Trails


Lecture 3 - Eulerian Circuits, Vertex Degrees and Counting


Lecture 4 - The Chinese Postman Problem and Graphic Sequences


Lecture 5 - Trees and Distance


Lecture 6 - Spanning Trees and Enumeration


Lecture 7 - Matchings and Covers


Lecture 8 - Independent Sets, Covers and Maximum Bipartite Matching


Lecture 9 - Weighted Bipartite Matching


Lecture 10 - Stable Matchings and Faster Bipartite Matching


Lecture 11 - Factors and Perfect Matching in General Graphs


Lecture 12 - Matching in General Graphs: Edmonds’ Blossom Algorithm


Lecture 13 - Connectivity and Paths: Cuts and Connectivity


Lecture 14 - k-Connected Graphs


Lecture 15 - Network Flow Problems


Lecture 16 - Vertex Coloring and Upper Bounds


Lecture 17 - Brooks’ Theorem and Color-Critical Graphs


Lecture 18 - Counting Proper Colorings


Lecture 19 - Planar Graphs


Lecture 20 - Characterization of Planar Graphs


Lecture 21 - Line Graphs and Edge-coloring


Lecture 22 - Hamiltonian Graph, Traveling Salesman Problem and NP-Completeness


Lecture 23 - Connected Dominating Set and Distributed Algorithm