Intensive Course on Graph Theory

Tiistai, syyskuu 15, 2015 (Koko päivä) - Perjantai, syyskuu 18, 2015 (Koko päivä)

VENUE: TS 107
START 15.9. at 13:15

COURSE TIMES (Subject to change)
TUE 13:15-15:30
WED 9:30-15:30
THU 9:30-15
FRI 9:30-12:30

NO PRE-REGISTRATION, Jjust show up in TS107 as the course starts!

 

Objectives

The objectives of this lecture is to give the main tools of graph theory and algorithmic to study optimization problems in telecommunication networks. The goal is to explain what kind of techniques
can be used to solve a problem depending on its complexity (polynomial or not) and on the particular structure of the instances.
 
The first day present the mathematical notions related to graphs and algorithms. Then, we focus on a particular example: the Problem of Routing and Wavelength Assignment (RWA) in optical networks.
Finally, we give a first approach on distributing computing by showing how to find a route in a network in a distributed way.

 

Course description

 
Basic on Graph Theory (5h)

We will first present the basic notions of graph theory (vertices, edges, degree, paths, cycles, distance) and illustrate them with the example of trees (acyclic graphs). Then, we will detail some
of the most famous graph algorithms such as Breadth First Search and Dijkstra Algorithm to compute distances in weighted graphs.
 
We then focus on the flow problem where a source must send some flow to a destination in a network where links have some capacity. We present the Ford-­‐Fulkerson algorithm to compute
the maximum possible flow to be sent. This allows us to present a first duality theorem relating the maximum flow and the minimum size of a cut.
 
For all the previous algorithms, we describe their time-­‐complexity: they are all polynomial in the size of the input.   
 
Basic on computational complexity and algorithms (4h)
 
We then give the basic knowledge on computational complexity, focussing on the difference between problems that can be solved in polynomial time (e.g., is a graph Eulerian?) and
NP-­‐hard problems (e.g., Hamiltonicity, Chromatic number).  
 
The notions of exact algorithms, approximation algorithms and heuristics are then presented.  
 
We give a first example of Linear Program in order to solve some graph problems.
 
Application to the RWA problem (6h)
 
Given a network and a set of requests (sources and destinations), the first problem is to compute a routing for satisfying the requests (i.e., find a route from the source to the
destination for each request) in such a way that the charge is minimized. That is, we aim at minimizing the maximum number of routes passing through the same link.

The second problem is to compute the minimum number of wavelengths required to assign one wavelength per route such that no two routes passing through the same link
share the same wavelength.
 
We study the computational complexity of these problems (showing they are NP-­‐hard) and provide different solutions (either exact but exponential, or approximations) using different methods such
as (Integer) Linear Programming.
 
Distributed algorithm (3h)
 
To conclude this lecture, we propose a different algorithmic perspective by studying distributed computing where each node has only a local view of the network. We mainly present the
routing problem where a message must reach its destination while having no global view of the topology. We show how the structure of the graph impact on the performance of compact routing
schemes.
 
Evaluation: the students will be given a list of exercises or will have to write an essay related to a topic of the course.
 

3 ECTS

 

Curriculum vitae
 

About the lecturer: Nicolas Nisse is a full-­‐time researcher (CR) at Inria Sophia Antipolis (France) since 2009, in the project-­‐team COATI. He received his engineer diploma from Supélec, in
2004, and received the Ph.D. degree from Laboratoire de Recherche en Informatique (LRI), in 2007. He got a postdoctoral position in University of Chile, Santiago, Chile (2007-­‐2008) and at Inria
(2008-­‐2009). His research interests include graph theory and algorithms. His work mainly focuses on Pursuit-­‐evasion games in graphs and on information spreading problems in telecommunication
networks (e.g. routing). His expertise concerns the design of algorithms using structural properties (e.g., graph decompositions) of networks.

 

Lisää kalenteriin

Takaisin tapahtumiin

Viimeksi päivitetty: 14.9.2015