Algorithmic Graph Theory

Course Name: 

Algorithmic Graph Theory (CS419)


B.Tech (CSE)


Programme Specific Electives (PSE)

Credits (L-T-P): 

03 (3-0-0)


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.


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.


Computer Science and Engineering

Contact us

Dr. Manu Basavaraju
Head of the Department
Department of CSE, NITK, Surathkal
P. O. Srinivasnagar, Mangalore - 575 025
Karnataka, India.
Hot line: +91-0824-2474053
Email: hodcse[AT]nitk[DOT]ac[DOT]in


Connect with us

We're on Social Networks. Follow us & get in touch.