Advanced Graph Theory
Indian Institute of Technology Kanpur , NPTEL and Indian Institute of Technology Patna via Swayam
-
26
-
- Write review
Overview
INTENDED AUDIENCE : UG & PG (both)PREREQUISITES : Discrete MathematicsINDUSTRY SUPPORT : Companies like Microsoft Research, Google,Facebook, LinkedIn and also start-ups are most eager to apply graph technology.
Syllabus
COURSE LAYOUT
Week 1 : Introduction to Graphs & its Applications, Basics of Paths, Cycles, and Trails, Connection, Bipartite Graphs, Eulerian Circuits, Vertex Degrees and Counting, Degree-sum formula, The Chinese Postman Problem and Graphic Sequences.Week 2 : Trees and Distance, Properties of Trees, Spanning Trees and Enumeration, Matrix-tree computation, Cayley's Formula, Prufer code.Week 3 : Matchings and Covers, Hall's Condition, Min-Max Theorem, Independent Sets, Covers and Maximum Bipartite Matching, Augmenting Path Algorithm, Weighted Bipartite Matching, Hungarian Algorithm.Week 4 : Stable Matchings and Faster Bipartite Matching, Factors & Perfect Matching in General Graphs, Matching in General Graphs: Edmonds’ Blossom AlgorithmWeek 5 : Connectivity and Paths: Cuts and Connectivity, k-Connected Graphs, Network Flow Ford-Fulkerson Labeling Algorithm, Max-Flow Min-cut Theorem, Menger's Proof using Max-Flow Min-Cut Theorem.Week 6 : Vertex Coloring and Upper Bounds, Brooks’ Theorem and Color-Critical Graphs, Counting Proper Colorings.Week 7 : Planar Graphs, Characterization of Planar Graphs, Kuratowski's Theorem, Wagner's Theorem.Week 8 : Line Graphs and Edge-coloring, Hamiltonian Graph, Traveling Salesman Problem and NP-Completeness, Dominating Sets.Taught by
Rajiv Misra
Related Courses
-
Introduction to Graph Theory
University of California, San Diego , Higher School of Economics
4.0 -
Discrete Mathematics
Shanghai Jiao Tong University
-
Graph Theory
Indian Institute of Science Education and Research, Pune, NPTEL, CEC
-
Introduction to Graduate Algorithms
Georgia Institute of Technology
-
Discrete Mathematics - IIITB
Indian Institute of Technology Bangalore, NPTEL
-
Graph Algorithms
University of California, San Diego
Reviews
0.0 rating, based on 0 reviews