3 credits (3-0-0)
Pre-requisites: COL351 OR Equivalent
Overlaps with: MTL468
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 therorem 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.