Computing the probability mass function of the maximum flow through a reliable network

Megha Sharma and Diptesh Ghosh

No WP2009-10-01, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: In this paper we propose a fast state-space enumeration based algorithm called TOP-DOWN capable of computing the probability mass function of the maximum s-t flow through reliable networks. The algorithm computes the probability mass function in the decreasing order of maximum s-t flow values in the network states. This order of enumeration makes this algorithm attractive for commonly observed reliable networks, e.g., in telecommunication networks where link reliabilities are high. We compare the performance of the TOP-DOWN algorithm with a path-based exact algorithm and show that the TOP-DOWN algorithm solves problem much faster and is able to handle much larger problems than existing algorithms.

Date: 2009-10-01
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.iima.ac.in/sites/default/files/rnpfiles/2009-10-01Sharma.pdf English Version (application/pdf)

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:iim:iimawp:8338

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().