Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Indian Institute of Technology Kanpur

Advanced Graph Theory

Indian Institute of Technology Kanpur , Indian Institute of Technology Patna and NPTEL via Swayam

This course may be unavailable.

Overview

Prepare for a new career with $100 off Coursera Plus
Gear up for jobs in high-demand fields: data analytics, digital marketing, and more.
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.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

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

Reviews

Start your review of Advanced Graph Theory

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.