Exact algorithms for NP-complete and hard problems

ECTS : 3

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.

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