Skip to main content
Kent Academic Repository

Maximal Flow in Branching Trees and Binary Search Trees

Bassetti, Federico, Leisen, Fabrizio (2011) Maximal Flow in Branching Trees and Binary Search Trees. Methodology and Computing in Applied Probability, 13 (3). pp. 475-486. ISSN 1387-5841. (doi:10.1007/s11009-010-9164-0) (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:36528)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided.
Official URL:
http://dx.doi.org/10.1007/s11009-010-9164-0

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.

Item Type: Article
DOI/Identification number: 10.1007/s11009-010-9164-0
Subjects: Q Science > QA Mathematics (inc Computing science) > QA273 Probabilities
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Mathematics, Statistics and Actuarial Science
Depositing User: Fabrizio Leisen
Date Deposited: 07 Jun 2014 09:31 UTC
Last Modified: 16 Nov 2021 10:13 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/36528 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.