Maximal Flow in Branching Trees and Binary Search Trees

Federico Bassetti () and Fabrizio Leisen ()
Additional contact information
Federico Bassetti: University of Pavia
Fabrizio Leisen: Universidad de Navarra

Methodology and Computing in Applied Probability, 2011, vol. 13, issue 3, 475-486

Abstract: 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: Branching trees; Binary search trees; Maximal flow in capacitated network; McKean trees; Random capacities; MSC 90B15; MSC 60G70 (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11009-010-9164-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:13:y:2011:i:3:d:10.1007_s11009-010-9164-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-010-9164-0

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().