For those of you that have followed the course
Advanced Algorithms:

Please note that the material of the course is available
at the copy center.


Course Program 2002-2003:

Basic Notions of graphs
Depth First Visit and Breadth First Visit: properties, type of edges
Algorithm for the shortest path problem:
-shortest paths from a single source with arbitrary cost of the edges
(dijkstra's and Bellmon Ford algorithms)
-all pair shortest paths (Floyd's algorithm)
-biconnected components

Eulerian Path:
-necessary and sufficient conditions for the existence of an eulerian path
-O(|E|^2) time algorithm for undirected graphs
-O(|E|) time algorithm for direct graphs

Hamiltoniam Path and Circuit:
-sufficient condition for the existence of an hamiltonian path/circuit
-necessary condition for the existence of an hamiltonian path/circuit

Coloring problems:
-lower bound
-bipartite graphs
-heuristics
-L(1)-labelling
_(L1,...,1)-labelling on regular grids
-L(2,1) & L(2,1,1)-labelling on regular grids
-L(\delta_1, \delta_2, ..., \delta_k)-labelling on regular grids

Approximation Algorithms:
*absolute approximation:
-absolute approximation for coloring of planar graphs
-absolute approximation for the maximum number of programs stored in two
disks
-NP-hardness of the absolute approximation problem of 0/1 integer knapsack
and clique problems
*relative approximation:
-NP-hardness of the relative approximation of the traveling salesman
problem
-relative approximation of the Longest Processing Time rule for the
scheduling of independent task
*approximation scheme:
-approximation scheme for the Longest Processing Time rule for the
scheduling of independent task
*polinomyal time approximation schemes (PTAS):
-rounding
-interval partitioning
-separation

Network Flow:
-problem definition, with Ford & Fulkerson algorithm
-O(N|E|^2) Edmonds & Karp algorithm