Algorithmic Graph Theory

Course Name: 

Algorithmic Graph Theory (CO464)


B.Tech (CSE)


Programme Specific Electives (PSE)

Credits (L-T-P): 

03 (3-0-0)


Basic definitions and terminology of graphs and digraphs, and introduction to simple complexity theory, How choice of graph traversals (e.g., depth-first and breadth-first searches) affect algorithmic efficiency, Spanning Trees, Connectivity. Circuit space, Planarity testing, genus of a graph, Networks and flows: max-flow/min-cut theorem and max-flow algorithms, Matching in weighted and unweighted graphs, Eulerian and Hamiltonian tours, Chinese postman and travelling salesman problems, Dominating sets, independence and cliques, Coloring graphs (including the famous 4-colour problem of planar graphs) NP-completeness and its importance in graph algorithms.


1. Alan Gibbons, "Algorithmic Graph Theory", Cambridge University Press, 1985.
2. Cormen, Leiserson and Rivest, "Introduction to Algorithms", McGraw-Hill, 1986.
3. James McHugh, "Algorithmic Graph Theory", Prentice-Hall, 1989.


Computer Science and Engineering

Contact us

Dr. Shashidhar G Koolagudi

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.