Exponential time algorithms S. Gaspers Introduction Exponential Time Algorithms Problem Definitions Algorithm Design Techniques Dynamic Programming across Subsets Branch & Reduce Memorization Treewidth Treewidth combined with Branch & Reduce Iterative Compression Inclusion-Exclusion Conclusion Introduction to Exponential Time Algorithms séminaire AlGco Serge Gaspers1 1LIRMM – Université Montpellier 2, CNRS January 22, 2009 1 / 50
- exponential time
- iterative compression
- treewidth
- inclusion-exclusion
- algorithms
- reduce
- hard problems
- algorithm design