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
4 MB (4375141 bytes)
Series
Algorithms and Combinatorics
Edition
1
Pages
172\172
Library
kolxoz
DPI
300
Time added
2009-07-20 03:45:11

Description

The book gives an accessible account of modern probabilistic methodsfor analyzing combinatorial structures and algorithms. It will be anuseful guide for graduate students and researchers. Special featuresincluded: a simple treatment of Talagrand's inequalities and theirapplications; an overview and many carefully worked out examples ofthe probabilistic analysis of combinatorial algorithms; a discussionof the "exact simulation" algorithm (in the context of Markov ChainMonte Carlo Methods); a general method for finding asymptoticallyoptimal or near optimal graph colouring, showing how theprobabilistic method may be fine-tuned to exploit the structure ofthe underlying graph; a succinct treatment of randomized algorithmsand derandomization techniques.

Similar books