Università Roma Tre

1. Introduction to graph theory: graph, directed graph, tree, rooted tree, connection, strong connection, acyclic graph; graphs isomorphisms, planarity, Kuratowski's theorem, Euler's formula; graph coloring; Eulerian paths, Hamiltonian circuits.

2. Theory of algorithms and optimization: recalls on algorithms and structured programming; computational complexity of an algorithm, complexity classes for problems, classes P, NP, NP-complete, NP-hard; decision-making, research, enumeration and optimization problems; non-linear programming problems, convex programming, linear programming and integer linear programming; combinatorial optimization problems.

Recalls on the elements of combinatorial calculation, algorithms for the generation of the set of parts of a finite set, permutations and combinations of the elements of a set, calculation of the binomial coefficient; the problem of the "Latin squares" and the game of Sudoku; a recursive algorithm for the solution of the game.

3. Optimization problems on graphs and network flows: graph visit, verification of fundamental properties of a graph: connection, strong connection, presence of cycles. Topological sorting of an directed acyclic graph.

The problem of the minimum spanning tree, Kruskal's algorithm, Prim's algorithm, formulation of the problem in terms of Integer Linear Programming.

Search for minimum cost paths on a weighed graph; minimum cost path with single source, Dijkstra's algorithm, Bellman-Ford's algorithm; minimum cost path between all pairs of vertices of the graph, dynamic programming algorithms, Floyd-Warshall's algorithm, transitive closure of a graph.

Network flows and the maximum flow on a network, Theorem of maximum flow and minimum cut, Ford-Fulkerson's algorithm, Edmonds-Karp's algorithm, preflow algorithm, "push-relabel" algorithm.

Problems of partitioning of graphs, trees and paths, problems for the optimal partitioning of trees and paths into p connected components; objective functions, algorithmic techniques for the solution of this class of problems (dynamic programming, linear programming, shifting).

Stable marriage problem, problem definition and matching stability criterion, applications, Gale and Shapley algorithm.

4. Programming laboratory for developing C language programs for the optimizations algorithms of algorithms in GNU/Linux environment and with Wolfram Mathematica software.

Cormen, Leiserson, Rivest, Stein, "Introduzione agli algoritmi e strutture dati", terza edizione, McGraw-Hill, 2010