Maximal flows in branching tress and binary search trees
Articles
Overview
published in
publication date
- September 2011
start page
- 475
end page
- 486
issue
- 3
volume
- 13
Digital Object Identifier (DOI)
International Standard Serial Number (ISSN)
- 1387-5841
Electronic International Standard Serial Number (EISSN)
- 1573-7713
abstract
- A capacitated network is a tree with a non negative number, called capacity, associated to each edge. The maximal f low that can pass through a given path is the minimun capacity on the path. Antal and Krapivski (Phys Rev E 74:051110, 2006) study the distribution for the maximal flow from the root to a leaf in the case of a deterministic binary tree with independent and identically distributed random capacities. In this paper their result is extended to three classes of trees with a random number of children and dependent random capacities: binary trees with general capacities distribution, branching trees with exchangeable capacities and random binary search trees