Combinatorial Optimization - Algorithms for telecommunications

The following lecture notes contain the material of several courses.
Chapters 1 to 6 correspond to the optional module Combinatorial Optimization of the FirstYear International Master in Computer Science. They arre prerequisite knowledge for the modules Algorithms for telecommunications I and II of the Master of Science in Ubiquitous Networking and Computing (2nd year)
In Algorithms for telecommunications I (first term), Chapters 7 to 10 are presented.
In Algorithms for telecommunications II (second term), some of the Chapters 13 to 19 are exposed.

Lectures notes

The lecture notes are continously improving. New chapters will be added as soon as they are available. Already available chapter are often updated (adding of new material or/and error correction).

Graph theory

  1. Basic concepts

  2. Searches in graphs and digraphs

  3. Complexity of algorithms

  4. Algorithms in edge-weighted graphs

  5. Connectivity

  6. Matchings in graphs

  7. Flows and applications

  8. Graph colouring

Linear Programming

  1. Linear Programming: Introduction and duality

  2. Polynomiality of Linear Programming

  3. Fractional relaxation

  4. Lagrangian relaxation

Applications to telecommunications

  1. Design of fault-tolerant on-board networks

  2. RWA

  3. GMPLS

  4. Radio channel assignment and (weighted) colouring

  5. Gathering

  6. Compact routing

  7. Protection