Algorithmic Graph Theory

Description

The course introduces classical concepts of pure and applied graph theory with emphasis on algorithms and their complexity. A wide variety of the most commonly used graph algorithms are given. Intractable graph problems with no known efficient solutions are identified and efficient approximation algorithms for their solution are studied. Topics will include connectivity, planarity, matching, network flows, graph colourability, Turan’s theorem and Ramsey numbers.

Program

Master in Computer Science

Objectives

• The student will:
  • Have an in-depth understanding of graph theory and its major classical theorems.
  • Know many of the widely used graph algorithms and their efficient implementation.
  • Be able to identify intractable graph problems and how to deal with them.
  • Know how to apply his knowledge to many practical applications like computer networks, transportation …etc.