You can find lecture notes here.

The following gathers most of the important notions taught during the lecture on ``Graph Algorithms and Optimization" of the Ubinet course.
Some of following slides have been done for a one-week school on Graph Theory and Optimization at University of Oulu, Finland, September 15-18th, 2015
• 0) Why is it useful?
Objectives of this school
• learn how to model problems (from various domains) using graphs
• know the available tools to handle these problem
• classical algorithms
• Linear Programming
• decide if a problem is ``easy" or ``difficult"
• know what to do when facing a ``difficult" problem
• exact exponential algorithms
• parameterized algorithms
• approximation algorithms
• heuristics
• 1) Introduction to Graphs
Many definitions to be remembered
• graph, vertex/vertices, edge
• neighbor, degree
• path, cycle
• connected graph
• tree
• subgraph, spanning subgraph
• 2) Weighted Graphs: Shortest Paths and Spanning Trees
• weighted graph, distances
• Deciding connectivity
• Shortest path tree in undirected graph O(|E|), (BFS)
• Computing Shortest path tree, (|E| + |V| log |V|) (Dijkstra)
• Computing Min. spanning tree O(|E| log |E|), (Kruskal)
Exercises
• 3) Flow: Ford-Fulkerson Algorithm
• flow, cut
• Ford-Fulkerson algorithm, O(|E| flowMax) for rational capacities
• Min Cut = Max Flow
• Menger Theorem (max number disjoint paths = min size of separator)
• Matching (Hungarian method, Edmonds algorithm, Hall Theorem)
Exercises
• 4) Computational Complexity (in brief)
• P, NP, NP-hard, NP-complete
• 3-SAT, Hamiltonian path, Coloring, Vertex Cover, ...
• Approximation algorithm
• 5) Introduction to Linear Programming
• linear programme.
• graphical method of resolution.
• Linear programs can be solved efficiently (polynomial-time).
• Integer programs are a lot harder (in general no known polynomial algorithms)
In this case, we look for approximate solutions.
Exercises
• 6) Introduction to Duality in LP
• How to compute a Dual Programme.
• Weak/Strong duality Theorem.
• Optimality certificate (Complementary Slackness).
Exercises
• 6.5) Model Graph Problems with LP
• Revisit graph problems (flow, shortest path, cuts, matching...) with LP
Exercises
• 7) Integer Linear Programming
• ILP allow to model many problems
• there may be a huge integrality gap (between OPT(LP) and OPT(ILP)).
• if no integrality gap (e.g., totally unimodular matrices), then Fractional Relaxation gives Optimal Integral Solution
• concrete example: RWA in WDM networks
• 8) Approximation Algorithms
• Minimum Vertex Cover vs. Maximum Matching
• Fractional relaxation is a method to obtain for some problems (Vertex Cover, Set Cover):
• Lower bounds on the optimal solution of an integer linear program (minimization).
• Polynomial approximation algorithms (with rounding).
• 9) Parameterized Algorithms
• Parameterized Problem: input (size n) + parameter k
• FPT algorithm: in time f(k) nO(1)
• Kernelization: Data reduction
• Kernelization <=> FPT
• Linear Kernel for Vertex Cover