Shortest Path Algorithm & Maximum -flow problem

Hi, I need your some specific information to prove the following two algorithm problems. I don't have specific information to answer these questions. Please reply.

[1] )Suppose that A is a matrix where A[i,j] is the length of a shortest path between vertices i and j in an undirected, weighted graph G with n vertices (all weights are positive). Design an algorithm that takes O(n2) time to update A when an additional edge is inserted into G.

[2] )Dining problem. Several families go out to dinner together. To increase their social interaction, they would like to sit at tables so that no two members of the same family are at the same table. Show how to find a seating arrangement that meets this objective (or prove that no such arrangement exists) by reducing this problem to the maximum-flow problem. Assume that there are p families and q tables; the i-th family has ai members, the j-th table has a seating capacity of bj.
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!