College of Computer & Information Science Spring 2005 Northeastern University Handout 15 CSU690: Algorithms and Data 30 March 2005

Problem Set 6 (due Wednesday, April 13)

1. (15 points) Bottleneck bandwidth

One can model a communication network by a weighted directed graph G, in which the vertices of G represent the nodes of the network, the edges of G represent the communication links of the network and the weight of an edge is the bandwidth of the link. We define the bottleneck bandwidth of a path p as the bandwidth of the minimum-bandwidth link in p.

Design and analyze an efficient algorithm to determine a path with the largest bottleneck bandwidth from a given node s to a given node t. If no path from s to t exists, then your algorithm must indicate so. Briefly justify the correctness of your algorithm. You may assume that the bandwidth of every link is positive. (Hint: Modify Dijkstra’s algorithm.)

2. (15 points) Arbitrage

Problem 24-3, page 615.

3. (10 points) Shortest paths on vertex-weighted graphs

Suppose you are given a connected undirected graph with weights on vertices (rather than on edges) and you are asked to compute the single-source shortest paths from a given source vertex. Here, the length of a path is defined as the sum of the weights on the vertices comprising the path. Give an algorithm for solving this problem by reducing it to the standard single-source shortest paths problem on directed graphs with weights on edges.

4. (10 points) Bellman-Ford algorithm

Exercise 25.1-5, page 628.

5. (10 points) Floyd-Warshall algorithm

Exercise 25.2–1, page 634.