CS124
Problem Set 8
Due on Friday, April 18th, 1997 in Pierce or 10DeWolfe #33
Please write the names of your collaborators on your problem sets!
1. Reliability
In the Single Source Shortest-Paths problem, you are given a graph with
a distance function on the edges, and a starting node,
and you are asked to find the shortest paths between the
start node and all other other nodes. Suppose you were
given a graph G=(V,E), and a reliability
function, r(e)=p, where e is an edge in
E, and 0 <= p <= 1 is the probability
that the edge e will not fail. Give an algorithm that
finds the most reliable paths between the start node and
all the other nodes.
2. Escaping 27.1 page 626
3. Updates 27-4 page 627
4. Show me the Algorithm 26.2-1 page 563
5. Difference Constraints 25.5-2 page 544
6. Factory Outlet Malls [Even] In the graph below, there are three
factories on the left that produce f1=5, f2=10, f3=5, and three consumers
that consume c1=5 c2=10 c3=5. Can all the requirements of this problem
be met simultaneously?
7. Steiner Trees
In most of the graph problems we talk about, we are restricted to
analyzing the nodes and edges given as input. Suppose this was no
longer the case. To start with a simple example, consider
4 nodes placed at the vertices of a unit square (pictured below).
The weight of the classicaly defined MST that is shown is 3.
Suppose you could place new junctions anywhere. Can
you construct a lighter MST that spans all of the original
nodes? What is the best you can do? In general, this
problem is very hard. It is also more applicable to real world problems.
8. Austin Texas
Austin Texas needs a new public transportation system. Assume that a
traveller should be able
to reach any of the large points on the grid below. Determine the cheapest
way to lay the tracks by specifying where the tracks should be laid. Junctions
can only occur at the large points. The tracks can be laid anywhere.
