Maximal flows in branching tress and binary search trees Articles uri icon

authors

  • LEISEN, FABRIZIO
  • BASSETTI, F.

publication date

  • September 2011

start page

  • 475

end page

  • 486

issue

  • 3

volume

  • 13

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