ENGLISH

Probabilistic Methods for Algorithmic Discrete Mathematics

By Michel Habib , Colin McDiarmid , Jorge Ramirez-Alfonsin , Michael Molloy (auth.) , Bruce Reed (eds.)

Book information

Publisher
Springer-Verlag Berlin Heidelberg
Year
1998
ISBN
3540646221, 9783540646228
DOI
10.1007/978-3-662-12788-9
LCC
QA164 .P74 1998
Google Books ID
Vx7FJy5JlcEC
Open Library ID
OL374419M
Language
english
Format
DJVU
Filesize
5 MB (5284531 bytes)
Series
Algorithms and Combinatorics 16
Edition
1
Pages
325\338
Orientation
no
Scanned
yes
Time added
2011-08-31 04:54:40
Combinatorics; Computation by Abstract Devices; Sy

Description

The book gives an accessible account of modern pro- babilistic methods for analyzing combinatorial structures and algorithms. Each topic is approached in a didactic manner but the most recent developments are linked to the basic ma- terial. Extensive lists of references and a detailed index will make this a useful guide for graduate students and researchers. Special features included: - a simple treatment of Talagrand 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 explit the structure of the underlying graph - a succinct treatment of randomized algorithms and derandomization techniques

Similar books