Graph Theory and related Algorithms

Objectives

“This course will enable students:

• To design efficient Graph Algorithms.
• To understand advanced graph theoretic concepts and laying fundamentals for research
• To understand approximation algorithms and design approximation algorithms for NP hard graph problems.

 The course will help   students who wants to prepare for GATE exam and to prepare for interviews for higher studies.”

Syllabus

“Introduction, Graph Theory Basics: Definition and basic concepts, Efficient representations of Graphs; Graph Searching: DFS and BFS; Application of Graph Searching: finding connected components, bi-connected components, testing for bipartite graphs, finding cycle in graph; Trees: Definitions and basic concepts. Paths and Distance in Graphs: Single source shortest path problem, All pairs shortest path problem, center and median of a graph, activity digraph and critical path; Hamiltonian Graphs: sufficient conditions for Hamiltonian graphs, traveling Salesman problem; Eulerian Graphs: characterization of Eulerian graphs, construction of Eulerian tour Planar Graphs: properties of planar graphs, a planarity testing algorithms; Graph Coloring: vertex coloring,  edge coloring, planar graph coloring;Matching: maximum matching in bipartite graphs, maximum matching in general graphs; Networks: The Max-flow min-cut theorem, max-flow algorithm; NP-Complete Graph problems; Approximation algorithms for some NP-Hard graph problems; Algorithms for some NP-Hard graph problems on special graph classes;”.