Algorithmic Graph Theory
Course Name:
Algorithmic Graph Theory (CS419)
Programme:
B.Tech (CSE)
Category:
Programme Specific Electives (PSE)
Credits (L-T-P):
03 (3-0-0)
Content:
Graphs, Preliminaries on graphs, Cardinality matching in bipartite graphs, Weighted matching in bipartite graphs, Edmonds matching algorithm for general graphs, Algorithms for vertex cover in bipartite graphs. Flow networks, Ford-fulkerson algorithm, Dinitz algorithm, Application of flows, Connectivity, Structure of mincuts, Algorithms for interval graphs, Chordal graphs, Tree-width, Algorithms based on tree-decompositions, Approximation algorithms, Parameterized algorithms, Exact exponential algorithms.
References:
R. Diestel, Graph Theory, Second edition, Springer, 2000.
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North Holland, 1976.
D. West, Introduction to Graph Theory, Second Edition, PHI, 2003.
A. Schrijver, A course in Combinatorial Optimization, Cambridge University Press, 2004.
T.H Cormen, C.E Leiserson, R.L. Rivest, C. Stein, Introduction To Algorithms, Third edition, PHI, 2009.
J. Kleinberg and E. Tardos, Algorithm Design, Pearson Education, 2006.
Department:
Computer Science and Engineering