Advanced Graph Theory (Prof. Rajiv Misra, IIT Patna) | Computer Science

Advanced Graph Theory

Advanced Graph Theory. Instructor: Prof. Rajiv Misra, Department of Computer Science and Engineering, IIT Patna. Advanced Graph Theory focuses on problem solving using the most important notions of graph theory with an in-depth study of concepts on the applications in the field of computer science. This course provides an in-depth understanding of Graphs and fundamental principles and models underlying the theory, algorithms, and proof techniques in the field of Graph Theory. Emerging applications of Graph Theory in Computer Science domain will be covered for significant impact. Upon completing this course, students will have intimate knowledge about how the graph theory play an important role to solve the technology driven and research oriented problems. (from nptel.ac.in)

Introduction

Lecture 01 - Graph Theory: Introduction

Lecture 02 - Paths, Cycles, and Trails

Lecture 03 - Eulerian Circuits, Vertex Degrees and Counting

Lecture 04 - The Chinese Postman Problem and Graphic Sequences

Lecture 05 - Trees and Distance

Lecture 06 - Spanning Trees and Enumeration

Lecture 07 - Matchings and Covers

Lecture 08 - Independent Sets, Covers and Maximum Bipartite Matching

Lecture 09 - 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 Graphs, Traveling Salesman Problem and NP-Completeness

Lecture 23 - Connected Dominating Set and Distributed Algorithm

References

Advanced Graph Theory
Instructor: Prof. Rajiv Misra, Department of Computer Science and Engineering, IIT Patna. This course provides an in-depth understanding of Graphs and fundamental principles and models underlying the theory, algorithms, and proof techniques in the field of Graph Theory.