Skip to main content

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)

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. (Contact us about this Publication)
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: Faculties > Sciences > School of Mathematics Statistics and Actuarial Science
Faculties > Sciences > School of Mathematics Statistics and Actuarial Science > Statistics
Depositing User: Fabrizio Leisen
Date Deposited: 07 Jun 2014 09:31 UTC
Last Modified: 01 Aug 2019 10:36 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/36528 (The current URI for this page, for reference purposes)
Leisen, Fabrizio: https://orcid.org/0000-0002-2460-6176
  • Depositors only (login required):