| Course Outline | General Information | Study Material | Lectures (classwise) |
The course consists of 4 lecture hours per week.
The basic thrust of the course would be to study Graph Algorithms from a combinatorial optimization standpoint. We will first focus on polynomially solvable problems in graphs mainly focussing on shortest paths, network flow, matching, etc. . We would then move towards NP-hard problems and approximation algorithms for them.
We will try to stick to the basic course outline as given in this page, but may deviate a bit.
We would assume in this course that you have undergone the Data and File Structures, Design and Analysis of Algorithms and Discrete Structures courses.
| Class Timings: | Monday 11:15-13:00, Wednesday 11:15-13:00 Room No. 719, S. N. Bose Bhavan (Library Building) |
| The necessary evil - marks, exam, etc.: | Mid-sem: 30, End-sem: 50, Internal evaluation: 20 |
| Books |
(B1) Algorithm Design J. Kleinberg and Eva Tardos Pearson Education (B2) Algorithmic Graph Theory and Perfect Graphs M. C. Golumbic Academic Press (B3) M. R. Garey and D. S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness Freeman (B4) Approximation Algorithms V. V. Vazirani Springer (B5) Approximation Algorithms for NP-Hard problems D. S. Hochbaum (edited) Thomson (B6) An Introduction to Algorithms T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein Prentice Hall India. (B7) Introduction to Graph Theory Douglas B. West Prentice Hall India (B8) Combinatorial Optimization: Algorithms and Complexity C. Papadimitriou and K. Steiglitz Prentice Hall of India |
| Web Resources |
(W1) Lecture Notes by Ron Shamir
(W2) Lecture Notes by Michel Goemans (W3) Lecture Notes by Samir Khuller (W4) Lecture Notes by Therese Biedl |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (01-08-11) |
Shortest path: Dijkstra's algorithm | - | (B6), (B1) |
| Lecture 2 (08-08-11) |
Network Flows | - | (B1), (B6) |
| Lecture 3 (10-08-11) |
Network Flows, Bipartite matching | - | (B6) |
| Lecture 4 (22-08-11) |
Network Flows: Preflow Push and relabel | - | (B1) |
| Lecture 5 (24-08-11) |
Network Flows: Preflow Push and relabel | - | (B1) |
| Lecture 6 (25-08-11) |
Matching: Berge's Theorem, Hall's Theorem | - | (B7) |
| Lecture 7 (29-08-11) |
Maximum Matching in Bipartite Graphs: Hopcroft and Karp's algorithm |
- | (B8), (W2), (W3) |
| Lecture 8 (05-09-11) |
Maximum Matching in Graphs: Edmond's blossom shrinking |
- | (B8), (W2) |
| Lecture 9 (07-09-11) |
Maximum Matching in Graphs: (Contd.) |
- | (B8),(W2) |
| Lecture 10 (08-09-11) |
Weighted Bipartite Matching | - | (W3) |
| Lecture 11 (12-09-11) |
Interval Graph | - | (B2), (W1), (W4) |
| Lecture 12 (14-09-11) |
Interval Graph | - | (B2), (W1), (W4) |
| Mid Semester | Model Solution | - | - |
| Lecture 13 (17-10-11) |
P and NP, Polynomial reducibility, NP-Completeness | - | (B1), (B3), (B6) |
| Lecture 14 (24-10-11) |
Approximation Algorithm, Inapproximibility results; Bin Packing, Vertex Cover |
- | (B4) |
| Lecture 15 (25-10-11) |
Minimum Makespan Scheduling, Inapproximability of TSP |
- | (B4) |
| Lecture 16 (31-10-11) |
Metric TSP, Introduction to (F)PTAS |
- | (B4) |
| Lecture 17 (01-11-11) |
FPTAS for integer knapsack | - | (B4) |
| Lecture 18 (02-11-11) |
Perfect graphs, Perfect Graph Theorem (statement only), Triangulated graphs |
- | (B2), (W1) |
| Lecture 19 (09-11-11) |
Characterizing Triangulated graphs | - | (B2), (W1) |
| Lecture 20 (14-11-11) |
Recognizing Triangulated graphs | - | (B2), (W1) |
| Lecture 21 (15-11-11) |
Triangulated graphs as Intersection graphs | - | (B2), (W1) |
| Lecture 22 (16-11-11) |
Triangulated graphs as Intersection graphs Triangulated graphs are Perfect |
- | (B2), (W1) |