- English
- فارسی

# 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

signicant 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.

A decent knowlege about graph theory, disrete mathemaics and algorithms.

Scribing (15%)+Homeworks(15%)+ Midterm (30%)+ Final(40%)+Projects (optional)

Saturdays-Mondays 13:00-15:00