More than 1,900 Springer Protocols eBooks at just $9.99 each! Get yours today>>

Algorithms and Combinatorics

Probabilistic Methods for Algorithmic Discrete Mathematics

Editors: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (Eds.)

Buy this book

eBook $149.00
price for USA (gross)
  • ISBN 978-3-662-12788-9
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $189.00
price for USA
  • ISBN 978-3-540-64622-8
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $189.00
price for USA
  • ISBN 978-3-642-08426-3
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
About this book

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

Table of contents (7 chapters)

  • The Probabilistic Method

    Molloy, Michael

    Pages 1-35

  • Probabilistic Analysis of Algorithms

    Frieze, Alan M. (et al.)

    Pages 36-92

  • An Overview of Randomized Algorithms

    Motwani, Rajeev (et al.)

    Pages 93-115

  • Mathematical Foundations of the Markov Chain Monte Carlo Method

    Jerrum, Mark

    Pages 116-165

  • Percolation and the Random Cluster Model: Combinatorial and Algorithmic Problems

    Welsh, Dominic

    Pages 166-194

Buy this book

eBook $149.00
price for USA (gross)
  • ISBN 978-3-662-12788-9
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $189.00
price for USA
  • ISBN 978-3-540-64622-8
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $189.00
price for USA
  • ISBN 978-3-642-08426-3
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Probabilistic Methods for Algorithmic Discrete Mathematics
Editors
  • Michel Habib
  • Colin McDiarmid
  • Jorge Ramirez-Alfonsin
  • Bruce Reed
Series Title
Algorithms and Combinatorics
Series Volume
16
Copyright
1998
Publisher
Springer-Verlag Berlin Heidelberg
Copyright Holder
Springer-Verlag Berlin Heidelberg
eBook ISBN
978-3-662-12788-9
DOI
10.1007/978-3-662-12788-9
Hardcover ISBN
978-3-540-64622-8
Softcover ISBN
978-3-642-08426-3
Series ISSN
0937-5511
Edition Number
1
Number of Pages
XVII, 325
Topics