Maximum Flow in Planar Networks with Exponentially Distributed Arc Capacities.

Abstract

This paper develops methods for the exact computation of the distribution of the maximum flow and related quantities in a planar network with independent and exponentially distributed arc capacities. A continuous time Markov chain (CTMC) with upper triangular rate matrix and single absorbing state is equal to the value of maximum flow in the network. Recursive algorithms are developed for computing the distribution and moments of the maximum flow. Algorithms are also presented to compute the probability that a given cut is the minimum capacity cut in the network. The algorithms are efficient and computationally stable. Distribution of the maximum flow, given a minimum cut, is studied. Keywords include: Maximum flow; Stochastic networks; Multi-state reliability modeling; Markov chains.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1984
Accession Number
ADA153158

Entities

People

  • V. G. Adlakha
  • V. G. Kulkarni

Organizations

  • University of North Carolina at Chapel Hill

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Absorption
  • Algorithms
  • Classification
  • Computations
  • Differential Equations
  • Equations
  • Flow Network
  • Markov Chains
  • Mathematics
  • North Carolina
  • Operations Research
  • Probability
  • Probability Distributions
  • Random Variables
  • Security
  • Stochastic Processes
  • Systems Analysis

Fields of Study

  • Engineering

Readers

  • Graph Algorithms and Convex Optimization.
  • Statistical inference.