Algebraic methods applied to shortest path and maximum flow problems in stochastic networks. Issue 2 (7th September 2012)

• Record Type: Journal Article
• Authors: Hastings, K. C.; Shier, D.R.; Gouveia, Luis; Voß, Stefan
• Is Part Of: Networks. Volume 61:Issue 2(2013:Mar.)
• Page Start: 117
• Page End: 127
• Publication Date: 2012-09-07
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21485
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>We present an algebraic approach for computing the distribution of the length of a shortest <italic>s</italic> ‐ <italic>t</italic> path, as well as the distribution of the capacity of a minimum <italic>s</italic> ‐ <italic>t</italic> cut, in a network where the arc values (lengths and capacities) have known (discrete) probability distributions. For each problem, both exact and approximating algorithms are presented. These approximating algorithms are shown to yield upper and lower bounds on the distribution of interest. This approach likewise provides exact and bounding distributions on the maximum flow value in stochastic networks. We also obtain bounds on the expected shortest path length as well as the expected minimum cut capacity (and the expected maximum flow value). © 2012 Wiley Periodicals, Inc. NETWORKS, 2013</p> </abstract>