Random Generation of Trees: Random Generators in Computer Science

by Laurent Alonso, Renï Schott

Overview

Random Generation of Trees is about a field on the crossroads between computer science, combinatorics and probability theory. Computer scientists need random generators for performance analysis, simulation, image synthesis, etc. In this context random generation of trees is of particular interest. The algorithms presented here are efficient and easy to code. Some aspects of Horton—Strahler numbers, programs written in C and pictures are presented in the appendices. The complexity analysis is done rigorously both in the worst and average cases.
Random Generation of Trees is intended for students in computer science and applied mathematics as well as researchers interested in random generation.

Product Details

ISBN-13:	9781441951502
Publisher:	Springer US
Publication date:	12/07/2010
Edition description:	Softcover reprint of hardcover 1st ed. 1995
Pages:	208
Product dimensions:	6.30(w) x 9.45(h) x 0.02(d)

Table of Contents

1 Introduction.- 2 Notations.- 3 Generation of Simple Kinds of Trees.- 4 Generation Using Bijective Methods.- 5 Generation of Forests of Trees Split into Patterns.- 6 Generation of Colored Trees.- 7 Two Methods of Generation by Rejection.- 8 Arborescences.- 9 Generation of Trees with a Given Height and Some Tricks about Complexity.- 10 A Parallel Algorithm for the Generation of Words.- Appendix 1 Horton-Strahler’s Numbers.- Appendix 2 Algorithms.- 2.1 Generation of binary trees: Rimy’s algorithm.- 2.2 Generation of unary-binary trees: Samaj Lareida’s algorithm.- Appendix 3 Pictures of Trees.- References.

Editorial Reviews

Johnny Appleseed would find little here to help his life work, but if he wanted to explore a frontier linking computer science, combinatorics, and probability theory, he could learn how to generate random patterns for such tasks as performance analysis, simulation, and image synthesis. Efficient algorithms that are usually easy to code, some aspects of Horton-Strahler numbers written in C, and pictures of trees generated by computers are among the information provided. Some sections are didactic for beginners and others highly technical for veterans. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews