IIT Patna · Computer Science

Advanced Graph Theory

Prof. Rajiv Misra · 24 free video lectures

24 video lectures. Topics: Graph Theory: Introduction; Paths, Cycles, and Trails; Eulerian Circuits, Vertex Degrees and Counting; The Chinese Postman Problem and Graphic Sequences; Trees and Distance; Spanning Trees and Enumeration; Matchings and Covers; Independent Sets, Covers and Maximum…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Graph Theory: Introduction
  2. Paths, Cycles, and Trails
  3. Eulerian Circuits, Vertex Degrees and Counting
  4. The Chinese Postman Problem and Graphic Sequences
  5. Trees and Distance
  6. Spanning Trees and Enumeration
  7. Matchings and Covers
  8. Independent Sets, Covers and Maximum Bipartite Matching
  9. Weighted Bipartite Matching
  10. Stable Matchings and Faster Bipartite Matching
  11. Factors & Perfect Matching in General Graphs
  12. Matching in General Graphs: Edmonds' Blossom Algorithm
  13. Connectivity and Paths: Cuts and Connectivity
  14. k-Connected Graphs
  15. Network Flow Problems
  16. Vertex Coloring and Upper Bounds
  17. Brooks' Theorem and Color-Critical Graphs
  18. Counting Proper Colorings
  19. Planar Graphs
  20. Characterization of Planar Graphs
  21. Line Graphs and Edge-coloring
  22. Hamiltonian Graph, Traveling Salesman Problem and NP-Completeness
  23. Connected Dominating Set and Distributed Algorithm
  24. Live Session 10-03-2021

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Patna.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights