Exact Exponential Algorithms

Computer scientists distinguish between fast and slow algorithms. Fast, or good, algorithms are those that run in polynomial time, meaning that the number of steps required to solve a given problem is bounded by some polynomial in the length of the input. All other algorithms are slow, or bad, and their running time is usually exponential this book is about bad algorithms. Most computer scientists believe that many natural problems cannot be solved using polynomial algorithms. The most famous group of hard problems is the NP-complete family it is likely that in order to solve such problems exactly we must spend exponential running time in the worst-case scenarios. The design and analysis of exact algorithms leads to a better understanding of hard problems and initiates interesting new combinatorial and algorithmic challenges. This book provides an introduction to the area and explains the most common algorithmic techniques, and the text is supported throughout with exercises and detailed notes for further reading.The book is intended for advanced students and researchers in computer science, operations research, optimization and combinatorics.