Credits: 3 (3-0-0)
Prerequisites: COL351 OR Equivalent
Description
Algorithms for computing maximum s-t flows in graphs: augmenting path, blocking flow, push-relabel, capacity scaling etc. Max-flow min-cut theorem and its applications. Algorithms for computing min-cuts in graphs, structure of min-cuts. Min-cost flows and applications: cycle cancelling algorithms, successive shortest paths, strongly polynomial algorithms. Maximum matching in bipartite and general graphs: Hall’s theorem, Tutte’s theorem, Gallai-Edmonds decomposition. Weighted bipartite matching, Edmonds Algorithm for Weighted Non-Bipartite Matching,T-joins and applications. Factor-Critical Graphs, Ear Decompositions, Graph orientations, Splitting Off, k-Connectivity Orientations and Augmentations, Arborescences and Branchings, Edmonds theorem for disjoint arborescences. Planar graphs, algorithms for checking planarity, planar-separator theorem and its applications. Intersection graphs, perfect graphs: polyhedral characterization, the strong perfect graph theorem, kinds of perfect graphs and algorithms on them. Treewidth, algorithm for computing tree width, algorithms on graphs with bounded tree width.
Prerequisite Tree
flowchart TD
COL751-209[COL751]
COL351-209 --> COL106-209[COL106]
COL106-209 --> COL100-209[COL100]
COL751-209 --> COL351-209[COL351]
classDef empty height:17px, fill:transparent, stroke:transparent;
classDef trueEmpty height:0px, width:0px;