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
- 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 Bipartite Matching
- Weighted Bipartite Matching
- Stable Matchings and Faster Bipartite Matching
- Factors & Perfect Matching in General Graphs
- Matching in General Graphs: Edmonds' Blossom Algorithm
- Connectivity and Paths: Cuts and Connectivity
- k-Connected Graphs
- Network Flow Problems
- Vertex Coloring and Upper Bounds
- Brooks' Theorem and Color-Critical Graphs
- Counting Proper Colorings
- Planar Graphs
- Characterization of Planar Graphs
- Line Graphs and Edge-coloring
- Hamiltonian Graph, Traveling Salesman Problem and NP-Completeness
- Connected Dominating Set and Distributed Algorithm
- 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