Exact algorithms for NP-complete and hard problems

Crédit : 3 ECTS
Langue du cours : anglais

Volume horaire

• CM : 15 h
• Volume horaire global (hors stage) : 15 h

Compétences à 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.)

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

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.)

Enseignant responsable

MICHAIL LAMPIS