Bounding flow-performance in probabilistic weighted networks

Heidi J. Strayer, Charles J. Colbourn

Research output: Contribution to journalArticlepeer-review


Summary & Conclusions -Much research has been done on computing connectivity-probability in probabilistic networks. More recently, the area has been expanded to other performance measures, such as maxflow & distance. These problems are, in general, NP-hard. Therefore efficiently computable, and accurate, lower & upper bounds are sought. This paper presents: 1) distance renormalization which generalizes the reliability renormalization algorithm of Harms & Colbourn for bounding probabilistic distances in bi-directional probabilistic weighted networks; 2) a mechanism based on non-planar duality for using this algorithm to bound probabilistic maxflow and mean maxflow. The results obtained via distance renormalization compare favorably with other current techniques for our suite of test cases.

Original languageEnglish (US)
Pages (from-to)3-10
Number of pages8
JournalIEEE Transactions on Reliability
Issue number1
StatePublished - 1997
Externally publishedYes


  • Average maxflow
  • Distance upper bound
  • Maxflow lower bound
  • Multistate link
  • Probabilistic network

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Electrical and Electronic Engineering


Dive into the research topics of 'Bounding flow-performance in probabilistic weighted networks'. Together they form a unique fingerprint.

Cite this