Description

This course is an introduction to graph theory, and presents differences between routing algorithms and network scheduling. The PRIM and EAGER PRIM algorithms are presented, as well as the DFS and BFS search concepts.

• Maximum flow problem and algorithms as Ford Fulkerson, Edmonds-Karp and Dinic’s.

• Shortest Path algorithm such as Dijkstra and Bellman-Ford.

• Matching Problem and algorithms.

Compétences requises

Basics of programming, Python programming language, Data Structure.

Compétences visées

• Describe the problems in graph representation,

• To define the problem as maximum flow, shortest path or matching problem and resolve it using the adequate algorithm.

• Programming with python to represent the graphs and using the algorithms to find the best solution to the problem.

Disciplines

• Informatique

Informations complémentaires

Key words: Network, algorithms, graphs, maximum flow, shortest path, matching problem

Bibliographie

• Graphs, Networks and Algorithms by Dieter Jungnickel

• Network Flow Algorithms by David Williamson, Cornell University

• Network Routing: Algorithms, Protocols, and Architectures by Deepankar Medhi and Karthik Ramasamy

Contacts

Responsable(s) de l'enseignement

• Rabih Amhaz