Learn · Second Level Algorithms
Lecture 25 of 60Week 5
Lecture 25: Invariants Maintained by Push Relabel Algorithm
Prof. Palash Dey · IIT Kharagpur
Credits and licence
- From
- Second Level Algorithms, IIT Kharagpur (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Lecture 1: Amortized Complexity: What and Why?
- Lecture 2: Aggregate Method and Its Use in Multi-Stack
- Lecture 3: Use of Aggregate Method in Amortized Analysis of Binary Counter, Accounting Method and its Applications in the Amortized Analysis of Multi-stack and Binary Counter
- Lecture 4: Potential Method and Its Use in the Amortized Analysis of Multi-stack and Binary Counter
- Lecture 5: Dynamic Table
- Lecture 6: Dynamic Table Cont.
- Lecture 7: Fibonacci Heap: Creation, Insertion
- Lecture 8: Fibonacci Heap: Extract Min
- Lecture 9: Fibonacci Heap: Pseudocode of Insertion, Extract Min
- Lecture 10: Fibonacci Heap: Decrease Key, Amortized Analysis of Insertion, Extract Min
- Lecture 11: Fibonacci Heap: Amortized Analysis of Decrease Key
- Lecture 12: Fibonacci Heap: Amortized Analysis Cont.
- Lecture 13: Fibonacci Heap: Amortized Analysis Cont., Introduction to Maximum Flow
- Lecture 14: Maximum Flow: Naive Greedy Approach
- Lecture 15: Maximum Flow: Residual Graph
- Lecture 16: Maximum Flow: Ford Fulkerson Method
- Lecture 17: Integrality of Maximum Flow
- Lecture 18: Maximum Flow, Layered Residual Graph
- Lecture 19: Maximum Flow, Edmond-Karp Algorithm
- Lecture 20: Maximum Flow, Dinic's Algorithm
- Lecture 21: Maximum Flow, Dinic's Algorithm Cont.
- Lecture 22: Dry Run of Ford-Fulkerson Method, Edmond-Karp Algorithm, and Dinic's Algorithm
- Lecture 23: Overview of Push Relabel Algorithm
- Lecture 24: Pseudocode and Dry Run of Push Relabel Algorithm
- Lecture 25: Invariants Maintained by Push Relabel Algorithm
- Lecture 26: Proof of Correctness of Push Relabel Algorithm: A Key Lemma
- Lecture 27: Proof of Correctness of Push Relabel Algorithm: Bounding Number of Relabel and Saturating Push Operations
- Lecture 28: Proof of Correctness of Push Relabel Algorithm: Bounding Number of Non-Saturating Push Operations
- Lecture 29: Generalization of Maximum Flow
- Lecture 30: Generalization of Maximum Flow Cont. Max Flow Min Cut Theorem
- Lecture 31: Maximum Flow Minimum Cut Cont., Maximum Bipartite Matching
- Lecture 32: Maximum Bipartite Matching
- Lecture 33: Hall's Marriage Theorem
- Lecture 34: Flow Path Decomposition
- Lecture 35: Stable Matching
- Lecture 36: Gale Shapley Algorithm
- Lecture 37: Gale Shapley Algorithm Cont.
- Lecture 38: Maximum Flow Based Minimum Cut Algorithm
- Lecture 39: Karger's Minimum Cut Algorithm
- Lecture 40: Karger-Stein Algorithm
- Lecture 41: Karger-Stein Algorithm Cont.
- Lecture 42: Maximum Cut in General Graph
- Lecture 43: Edmond's Blossom Algorithm
- Lecture 44: Edmond's Blossom Algorithm Cont.
- Lecture 45: Edmond's Blossom Algorithm Cont.
- Lecture 46: Edmond's Blossom Algorithm Cont.
- Lecture 47: Edmond's Blossom Algorithm Cont.
- Lecture 48: Edmond's Blossom Algorithm Cont., Order Statistics
- Lecture 49: Order Statistics
- Lecture 50: Order Statistics Cont.
- Lecture 51: Linear Time Selection
- Lecture 52: Linear Time Selection Cont.
- Lecture 53: String Matching: KMP Algorithm
- Lecture 54: String Matching: KMP Algorithm Cont.
- Lecture 55: Introduction to NP
- Lecture 56: Self Reduction
- Lecture 57: NP Completeness
- Lecture 58: NP Completeness of 3 SAT
- Lecture 59: NP Completeness of Clique and Independent Set
- Lecture 60: NP Completeness of Vertex Cover and Subset Sum