Algorithmic Graph Theory

Course Name: 

Algorithmic Graph Theory (CO464)

Programme: 

B.Tech (CSE)

Category: 

Programme Specific Electives (PSE)

Credits (L-T-P): 

03 (3-0-0)

Content: 

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.

References: 

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.

Department: 

Computer Science and Engineering
 

Contact us

P Santhi Thilagam
Associate Professor and Head
Department of CSE, NITK, Surathkal
P. O. Srinivasnagar, Mangalore - 575 025
Karnataka, India.

  • Hot line: +91-0824-2474060

Connect with us

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