Random Trees: An Interplay between Combinatorics and Probability / Edition 1

Random Trees: An Interplay between Combinatorics and Probability / Edition 1

by Michael Drmota
     
 

ISBN-10: 3211999140

ISBN-13: 9783211999141

Pub. Date: 11/05/2010

Publisher: Springer Vienna

Trees are a fundamental object in graph theory and combinatorics as well as a basic object for data structures and algorithms in computer science. During the last years research related to (random) trees has been constantly increasing and several asymptotic and probabilistic techniques have been developed in order to describe characteristics of interest of large

…  See more details below

Overview

Trees are a fundamental object in graph theory and combinatorics as well as a basic object for data structures and algorithms in computer science. During the last years research related to (random) trees has been constantly increasing and several asymptotic and probabilistic techniques have been developed in order to describe characteristics of interest of large trees in different settings.

The aim of this book is to provide a thorough introduction into various aspects of trees in random settings and a systematic treatment of the involved mathematical techniques. It should serve as a reference book as well as a basis for future research. One major conceptual aspect is to bridge combinatorial and probabilistic methods that range from counting techniques (generating functions, bijections) over asymptotic methods (saddle point techniques, singularity analysis) to various sophisticated techniques in asymptotic probability (martingales, convergence of shastic processes, concentration inequalities).

Read More

Product Details

ISBN-13:
9783211999141
Publisher:
Springer Vienna
Publication date:
11/05/2010
Edition description:
Softcover reprint of hardcover 1st ed. 2009
Pages:
458
Product dimensions:
6.14(w) x 9.21(h) x 0.96(d)

Table of Contents

Classes of Random Trees.- Generating Functions.- Advanced Tree Counting.- The Shape of Galton-Watson Trees and Pólya Trees.- The Vertical Profile of Trees.- Recursive Trees and Binary Search Trees.- Tries and Digital Search Trees.- Recursive Algorithms and the Contraction Method.- Planar Graphs.

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >