Suppose we have a set of mobile nodes V, and at a particular point in time, there is a set E0 of edges among these nodes. As the nodes move, the set of edges changes from E0 to E1, then to E2, then to E3, and so on, to an edge set Eb. For i = 0 ~ b, let Gi denote the graph(V,Ei). So if we were to watch the structure of the network on the nodes V as a "time lapse," it would look precisely like the sequence of graphs G0 ~ Gb. We will assume that each of these graphs Gi is connected.
Now consider two particular nodes s, t in V. For an s-t path P in one of the graphs Gi, we define the length of P to be simply the number of edges in P, and we denote this l(P). Our goal is to produce a sequence of paths P0 ~ Pb so that for each i, Pi is an s-t path in Gi. We want the paths to be relatively short. We also do not want there to be too many changes--- points at which the identiy of the path switches. Formally, we define changes(P0,...,Pb) to be the number of indices i (0 <= i <= b-1) for which Pi != Pi+1. Fix a constant K > 0, we define the cost of the sequence of paths P0~ Pb to be cost(P0, ..., Pb) = sum from i = 0 ~ b of (l(pi) + K*changes(P0~Pb)). Now, the question is, how to give a polynomial-time algorithm to find a sequence of paths P0 ~ Pb of minimum cost, where Pi is an s-t path in Gi for i = 0 ~ b. Anyone knows how to solve this? P.S. By dynamic programming. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
