Maximal Flow in Branching Trees and Binary Search Trees |
| |
Authors: | Federico Bassetti Fabrizio Leisen |
| |
Institution: | 1.Department of Mathematics,University of Pavia,Pavia,Italy;2.Faculty of Economics,Universidad de Navarra,Pamplona,Spain |
| |
Abstract: | A capacitated network is a tree with a non negative number, called capacity, associated to each edge. The maximal flow 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|