Due on 24 September 2004 at noon.

CSE 591 Assignment One

  1. Let G=(V,E) be an undirected graph, and consider the all-terminal operation on G. Suppose that e={x,y} is an edge of G, and that z is a vertex different from x and y. Form a graph G' by removing the edge e and adding the edges e'={x,z} and e''={y,z}, so that p_e = p_{e'} = p_{e''}.

    Establish a relationship between the all-terminal reliability of G and that of G'. Explain/prove.

  2. Let G=(V,E) be an undirected graph, and let s and t be target vertices in a two-terminal operation on G. Let v be a vertex different from s and t, and let I be the set of edges incident with v. Form a new graph G' as follows: Add two new vertices v' and v''. Now for each edge in I, replace v in that edge either by v' or v''. Then delete vertex v. In each such substitution, the edge operation probability does not change.

    Establish a relationship between the two-terminal reliability of G and that of G'. Explain/prove.

  3. Let G=(V,E) be an undirected graph. Suppose that {s,t} is a subset of K, K is a subset of K', and K' is a subset of V.

    Establish a relationship between the k-terminal reliability of G for target set K and the k-terminal reliability of G for target set K'. Explain/prove.

  4. Implement a basic complete state enumeration algorithm for k-terminal reliability; explain any decisions you made to improve efficiency, but DO GENERATE ALL STATES to test them for operation.

  5. Implement a factoring method for two-terminal reliability using series-parallel reductions. Discuss your implementation.
For the programming, choose any language you like. Do not spend a lot of time on bells and whistles -- your main task is to get a basic easy-to-use program that you can do some simple tests on.

Email me if you have tried hard to figure out what to do, but have questions that you need answered.