ENGLISH

Probabilistic methods for algorithmic discrete mathematics

By Michel Habib , Colin McDiarmid , Jorge Ramirez-Alfonsin , Bruce Reed

Book information

Publisher
Springer
Year
1998
ISBN
9783540646228, 3-540-64622-1
LCC
QA164 .P74 1998
Language
english
Format
DJVU
Filesize
2 MB (2556526 bytes)
Series
Algorithms and Combinatorics
Edition
1
Pages
344\344
Library
Kolxo3
DPI
300
Time added
2009-07-20 03:45:11

Description

The book gives an accessible account of modern probabilistic methods for analyzing combinatorial structures and algorithms. It will be an useful guide for graduate students and researchers. Special features included: a simple treatment of Talagrand's inequalities and their applications; an overview and many carefully worked out examples of the probabilistic analysis of combinatorial algorithms; a discussion of the "exact simulation" algorithm (in the context of Markov Chain Monte Carlo Methods); a general method for finding asymptotically optimal or near optimal graph colouring, showing how the probabilistic method may be fine-tuned to exploit the structure of the underlying graph; a succinct treatment of randomized algorithms and derandomization techniques.

Similar books