by Fedor V. Fomin and Dieter Kratsch
Springer, 2010, 204 p.
http://dx.doi.org/10.1007/978-3-642-16533-7
Description:
Today most computer scientists believe that NP-hard problems cannot be
solved by polynomial-time algorithms. From the polynomial-time
perspective, all NP-complete problems are equivalent but their
exponential-time properties vary widely. Why do some NP-hard problems
appear to be easier than others? Are there algorithmic techniques for
solving hard problems that are significantly faster than the
exhaustive, brute-force methods? The algorithms that address these
questions are known as exact exponential algorithms.
The history of exact exponential algorithms for NP-hard problems dates
back to the 1960s. The two classical examples are Bellman, Held and
Karp's dynamic programming algorithm for the traveling salesman
problem and Ryser's inclusion–exclusion formula for the permanent of a
matrix. The design and analysis of exact algorithms leads to a better
understanding of hard problems and initiates interesting new
combinatorial and algorithmic challenges. The last decade has
witnessed a rapid development of the area, with many new algorithmic
techniques discovered. This has transformed exact algorithms into a
very active research field. 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.
Fedor Fomin
http://www.ii.uib.no/~fomin/
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
