2
Advanced Graph Theory. Instructor: Prof. Rajiv Misra, Department of Computer Science and Engineering, IIT Patna.
638 years, 9 months
23
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)
Course Currilcum
- Lecture 01 – Graph Theory: Introduction Unlimited
- Lecture 02 – Paths, Cycles, and Trails Unlimited
- Lecture 03 – Eulerian Circuits, Vertex Degrees and Counting Unlimited
- Lecture 04 – The Chinese Postman Problem and Graphic Sequences Unlimited
- Lecture 05 – Trees and Distance Unlimited
- Lecture 06 – Spanning Trees and Enumeration Unlimited
- Lecture 07 – Matchings and Covers Unlimited
- Lecture 08 – Independent Sets, Covers and Maximum Bipartite Matching Unlimited
- Lecture 09 – Weighted Bipartite Matching Unlimited
- Lecture 10 – Stable Matchings and Faster Bipartite Matching Unlimited
- Lecture 11 – Factors and Perfect Matching in General Graphs Unlimited
- Lecture 12 – Matching in General Graphs: Edmonds’ Blossom Algorithm Unlimited
- Lecture 13 – Connectivity and Paths: Cuts and Connectivity Unlimited
- Lecture 14 – k-Connected Graphs Unlimited
- Lecture 15 – Network Flow Problems Unlimited
- Lecture 16 – Vertex Coloring and Upper Bounds Unlimited
- Lecture 17 – Brooks’ Theorem and Color Critical Graphs Unlimited
- Lecture 18 – Counting Proper Colorings Unlimited
- Lecture 19 – Planar Graphs Unlimited
- Lecture 20 – Characterization of Planar Graphs Unlimited
- Lecture 21 – Line Graphs and Edge-Coloring Unlimited
- Lecture 22 – Hamiltonian Graphs, Traveling Salesman Problem and NP-Completeness Unlimited
- Lecture 23 – Connected Dominating Set and Distributed Algorithm Unlimited
