Paper Info
Title
Limit laws for terminal nodes in random circuits with restricted fan-out: a family of graphs generalizing binary search trees.
Abstract
We introduce a family of graphs C(n;i;s;a) that generalizes the binary search tree. The graphs represent logic circuits with fan-in i, restricted fan-out s, and arising by n progressive additions of random gates to a starting circuit of a isolated nodes. We show via martingales that a suitably normalized version of the number of terminal nodes in binary circuits converges in distribution to a normal random variate.
Year
DOI
Venue
2004
10.1007/s00236-004-0152-0
Acta Inf.
Keywords
DocType
Volume
Information System,Operating System,Data Structure,Communication Network,Information Theory
Journal
41
Issue
ISSN
Citations 
2-3
0001-5903
2
PageRank 
References 
Authors
0.51
2
2
Name
Order
Citations
PageRank
Hosam M. Mahmoud118355.63
Tatsuie Tsukiji2507.14