Learn · NPTEL

Course10610417024 lectures

Advanced Graph Theory

Prof. Rajiv Misra · IIT Patna

Start with lecture 1 At NPTEL

Lectures

Week 01

  1. Graph Theory: Introduction Video
  2. Paths, Cycles, and Trails Video
  3. Eulerian Circuits, Vertex Degrees and Counting Video

Week 02

  1. The Chinese Postman Problem and Graphic Sequences Video
  2. Trees and Distance Video
  3. Spanning Trees and Enumeration Video

Week 03

  1. Matchings and Covers Video
  2. Independent Sets, Covers and Maximum Bipartite Matching Video
  3. Weighted Bipartite Matching Video

Week 04

  1. Stable Matchings and Faster Bipartite Matching Video
  2. Factors & Perfect Matching in General Graphs Video
  3. Matching in General Graphs: Edmonds' Blossom Algorithm Video

Week 05

  1. Connectivity and Paths: Cuts and Connectivity Video
  2. k-Connected Graphs Video
  3. Network Flow Problems Video

Week 06

  1. Vertex Coloring and Upper Bounds Video
  2. Brooks' Theorem and Color-Critical Graphs Video
  3. Counting Proper Colorings Video

Week 07

  1. Planar Graphs Video
  2. Characterization of Planar Graphs Video

Week 08

  1. Line Graphs and Edge-coloring Video
  2. Hamiltonian Graph, Traveling Salesman Problem and NP-Completeness Video
  3. Connected Dominating Set and Distributed Algorithm Video

Live Session

  1. Live Session 10-03-2021 Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Patna
Department
Computer Science and Engineering
Teacher
Prof. Rajiv Misra
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge. Coordinated by IIT Kanpur.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed