Description
1. (30) Shortest Paths on Graphs using Bellman-Ford Algorithm. Consider the
directed graph shown. The numbers on the edges indicate costs of these edges.
(a) (15 Points) Find the shortest paths from all nodes to destination t, using the BellmanFord algorithm. Show (some of) your intermediate steps and the final result in the
following form: [next hop][distance to t] for every node.
(b) (15 Points) After the algorithm reaches steady state, somebody cuts off edges e-t
and b-d at the same time. Use Bellman-Ford to recalculate the paths to t after the
change. Does the algorithm converge? If yes, show your calculations and the final
“[next hop][destination] for every node. If not, explain why.
2. (45 Points) Finding Max Flow. Consider the directed graph shown in the figure below.
The numbers on the edges indicate capacities.
(a) (15 Points) Find the max-flow from the source (node 1) to the sink (node 7).
(b) (15 Points) Identify the min-cut corresponding to the max-flow you found in (a).
(c) (15 Points) Now assume that the capacity of edge 2-6 changes from 9 to 2. Find the
max flow on this new graph without recomputing it from scratch, but starting from the
solution you found in (a) and incrementally updating it.
i. Describe an algorithm that does that incremental update.
1
ii. Argue that it indeed finds the optimal solution (max flow for the new graph).
iii. Analyze its running time (it should be less than running Ford-Fulkerson from scratch).
iv. Run your algorithm and report the new max flow.
3. (25 Points) Consider a set of mobile computing clients who need to be connected to one of
several possible base stations. We’ll suppose there are n clients, with the position of each
client specified by its (x, y) coordinates in the plane. There are also k base stations; the
position of each of these is specified by (x, y) coordinates as well.
For each client, we wish to connect it to exactly one of the base stations. Our choice of
connections is constrained in the following ways. There is a range parameter r ; a client can
only be connected to a base station that is within distance r. There is also a load parameter
L; no more than L clients can be connected to any single base station.
(a) (10 Points) Design a polynomial-time algorithm for the following problem. Given the
positions of a set for clients and a set of base stations, as well as the range and load parameters, decide whether every client can be connected simultaneously to a base station,
subject to the range and load conditions.
(b) (10 Points) Write the condition of the feasible solution (i.e., connecting all clients to
base stations).
(c) (5 Points) Analyze the running time of your algorithm.
2
