Probabilistic Methods for Algorithmic Discrete Mathematics
By: edited by Michel Habib, Colin McDiarmid, Jorge Ramirez-Alfonsin, Bruce Reed
Contributors: McDiarmid, Colin; Ramirez-Alfonsin, Jorge; Reed, Bruce
Series: Algorithms and Combinatorics -- 16; Algorithms and Combinatorics -- 16
Publisher: Springer Berlin Heidelberg
Published: 1998
Place of publication: Berlin, Heidelberg
Language: eng
Format: [electronic resource] /
Number of pages: 325
ISBN-13: 9783642084263; 9783662127889
Subjects: Computer science; Data processing; Algebra; Combinatorics; Mathematics; Distribution (Probability theory)
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.
Notes: Online full text is restricted to subscribers.

Also available in print.

Mode of access: World Wide Web.
Table of contents: title: An Overview of Randomized Algorithms by R.Motwani, P.Raghavan; title: Concentration by C.McDiarmid; title: The Probabilistic Method by M.Molloy; title: Percolation and the Random Cluster Model: Combinatorial and Algorithmic Problems by D.Welsh; title: Mathematical Foundations of the Markov Chain Monte Carlo Method by M.Jerrum; title: Probabilistic Analysis of Algorithms by A.M.Frieze, B.Reed; title: Branching Processes and Their Applications in the Analysis of Tree Structures and Tree Algorithms by L.Devroye.