Tag Archives: probability

The network reliability problem and star semirings

In a previous post I defined the network reliability problem. Briefly, we are given a directed graph whose edges are labelled with probabilities, which we can think of as giving the likelihood of a message successfully traversing a link in … Continue reading

Posted in math | Tagged , , , , , | 9 Comments

The network reliability problem

Let be a directed graph with vertices and edges . Multiple edges between the same pair of vertices are allowed. For concreteness’ sake, think of the vertices as routers, and the edges as (one-way) connections. Let denote the set of … Continue reading

Posted in math | Tagged , , , | 17 Comments