Algorithmic Graph Theory
Course Name:
Algorithmic Graph Theory (CO464)
Programme:
Category:
Credits (L-T-P):
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.