Tag Archives: graph

Computing Eulerian paths is harder than you think

Everyone who has studied any graph theory at all knows the celebrated story of the Seven Bridges of Königsberg, and how Euler gave birth to modern graph theory while solving the problem. Euler’s proof is clever, incisive, not hard to … Continue reading

Posted in learning | Tagged , , , , | 5 Comments

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