COL751
| COL751 | |
|---|---|
| Algorithmic Graph Theory | |
| Credits | 3 |
| Structure | 3-0-0 |
| Pre-requisites | COL351 OR Equivalent |
| Overlaps | |
COL751 : Algorithmic Graph Theory
[edit]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.