THE RANDOM GENERATION OF DIRECTED ANIMALS

Authors
BARCUCCI E PINZANI R SPRUGNOLI R
Citation
E. Barcucci et al., THE RANDOM GENERATION OF DIRECTED ANIMALS, Theoretical computer science, 127(2), 1994, pp. 333-350
Citations number
9
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
127
Issue
2
Year of publication
1994
Pages
333 - 350
Database
ISI
SICI code
0304-3975(1994)127:2<333:TRGODA>2.0.ZU;2-Q
Abstract
In this paper, we propose an algorithm to randomly generate a directed animal. Directed animals are well-known combinatorial objects and hav e been widely used for modelling the physical phenomenon of percolatio n. The algorithm consists of three steps, and we prove that each of th em is performed in linear time. Finally, we report the results of our experiments made by means of appropriate computer programs in order to give empirical evidence that our algorithm really works.