Ects : 3

Enseignant responsable :

• MICHAIL LAMPIS

Volume horaire : 15

Description du contenu de l'enseignement :

The course presents the main techniques and tools for the design and analysis of exact algorithms for NP-complete/hard problems, as well as examples of applications of such algorithms and techniques.

Pré-requis recommandés :

Familiarity with graph theory and data structure will be useful

Pré-requis obligatoires :

Undergraduate level acquaintance with algorithms, running time analysis, computational complexity

Compétence à acquérir :

• Exact solution methods (Dynamic programming, Search trees, Enumeration, Inclusion – exclusion, Local search) and tools for their complexity evaluation
• Applications (Coloring, TSP, Independent Set, Cut, Set Covering)
• Techniques for the design of parameterized algorithms (Kernelization, Search trees, Random separation, Color coding, etc.)
• Applications (Vertex cover, Feedback vertex set, k-Covering, etc.)

Bibliographie, lectures recommandées

• Exact solution methods (Dynamic programming, Search trees, Enumeration, Inclusion – exclusion, Local search) and tools for their complexity evaluation
• Applications (Coloring, TSP, Independent Set, Cut, Set Covering)
• Techniques for the design of parameterized algorithms (Kernelization, Search trees, Random separation, Color coding, etc.)
• Applications (Vertex cover, Feedback vertex set, k-Covering, etc.)