A large collection of mobile wireless devices can naturally form a network in which the devices are the nodes, and two devices x and y are connected by an edge if they are able to directly communicate with each other (e.g., by a short-range radio link). Such a network of wireless devices is a highly dynamlc object, in which edges can appear and disappear over time as the devices move around. For instance, an edge (x, y) might disappear as x and y move far apart from each other and lose the ability to communicate directly. In a network that changes over time, it is natural to look for efficient ways of maintaining a path between certain designated nodes. There are Exercises two opposing concerns in maintaining such a path: we want paths that are short, but we also do not want to have to change the path frequently as the network structure changes. (That is, wed like a single path to continue working, if possible, even as the network gains and loses edges.) Here is a way we might model this problem. 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 E~, then to E2, then to E3, and so on, to an edge set Eb. Fir i = 0, 1, 2 ..... b, let G~ denote the graph (V, E~). 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 Go, G~, G2 .....Gb_~, G~. We will assume that each of these graphs G~ is connected. Now consider two particular nodes s, t ~ 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 g(P). Our goal is to produce a sequence of paths P0, P~ ..... P~ so that for each i, Pg is an s-t path in G~. We want the paths to be relatively short. We also do not want there to be too many changes--points at which the identity of the path switches. Formally, we define changes(Po, P~ .....P~) to be the number of indices i (0 < i < b - 1) for which Pi # P~+I" Fix a constant K > 0. We define the cost of the sequence of paths PO, P1 ..... Pb tO be b COSt(Po, PI ..... Pb) = ~ f-(Pi) + K. changes(Po, P~ ..... Pb).

(a) Suppose it is possible to choose a single path P that is an s-t path in each of the graphs Go, G~ .....Gb. Give a polynomial-time algorithm to find the shortest such path.

(b) Give a polynomial-time algorithm to find a sequence of paths P0, P~ .....P~ of minimum cost, where P~ is an s-t path in G~ for i=0,1 .....b.