Graph and Algorithms- Undergraduate

Course title: Graphs & Algorithms
Instructor: Ramin Javadi
Tel. 3391 3657.
Email: rjavadi@iut.ac.ir

References:
1-Graph Theory, J.A. Bondy and U.S.R. Murty, 2008.
2- Approximation algorithm, V. Vazirani, 2001.
3- Design of approximation algorithms, D. Williamson, D. Shmoys, 2010.
4- Algorithms, S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, 2006.

Outline: This is a secondary course in graph theory which is aimed to study some
signicant developments and powerful tools in graph theory with avour of algorithms.
At the end, students are supposed to acquire the main techniques in computational and
algorithmic aspects of graph theory. The course discusses the known ecient algorithms
for some important problems as well as some negative news in the sense that no ecient
algorithm is possible. Thus, it will be an amalgamation of the algorithm design and the
computational complexity. The course is oered to the students familiar with the basic
concepts of graph theory and is organized to provide them with necessary knowledge to
get ready for entering professional research.

Note: The materials of the course will be provided online in the learning management system (lms) and the assignments will be proposed and collected there.

Topics:
1. Complexity of algorithms: Classes P, NP and Co-NP. Reductions. NP-complete
problems.
2. Matching theory: Bipartite and non-bipartite graphs. Hungarian and Edmonds'
algorithms. Weighted Matching and LP formulation.
3. Approximation algorithms: Greedy Approximation Algorithms. Dynamic Program-
ming and Weakly Polynomial-Time Algorithms. Relaxation and Rounding Tech-
niques. Linear Programming Relaxations. Randomized Rounding.
4. The probabilistic method.
5. Connectivity: Flows and cuts, Multicommodity flow, Sparsest cut and expanders,
Multicut and max cut, Gomory-Hu tree.
6. Travelling salesman problem: Euclidean and non-Euclidean.
7. Treewidth and algorithmic application: Baker's method.
8. Graph Minors.