A dynamic programming language formulation for a k-stage graph problem is obtained by first noticing that every s to t path is the result of a sequence of k-2 decisions. The ith decision involves determining which vertex in Vi+11≤ i ≤ k -2 is to be on the path. It is easy to see that principle of optimality holds. Let p(i, j) be a minimum cost path from vertex j in Vi to vertex t. Let cost (i , j) be the cost of the path. Then using the forward approach, we obtain

Cost(i, j) = l min € <j, l > € E Vi+1 “{ c(i, j) + cost (i+1, l ) }

Since cost (k-1, j) = c(j, t) if < j, k > € E and cost (k-1, j ) = ∞ if < j , t > doesnot belongs to E may be solved for all j € V k-2 then cost (k-3, j ) for all j € V k-2 then cost (k-3, j) for all j € V k-3 and so on finally cost (1, s ) – 1.

F cost (3,6) = min { 6+ cost (4,9), 5 + cost (4, 10) }
= min { 6 + 4, 5+ 2}
= 7

F cost (3,7) = min { 4+ cost (4,9), 3 + cost (4, 10) }
= min { 4+ 4, 3+ 2}
= 5

F cost (3,8) = min { 5+ cost (4,10), 6 + cost (4, 11) }
= min { 5+2 , 6+ 5}
= 7

F cost (2, 2) = min { 4+ cost (3,6), 2 + cost (3, 7), 1+ cost (3, 8) }
= min { 4 +7, 2+ 5 , 1+ 7}
= 7

F cost (2, 3) = min { 2+ cost (3,6), 7 + cost (3, 7) }
= min { 2 + 7, 7+ 5}
= 9

F cost (2, 4) = min { 11+ cost (3, 8) }
= min { 11, 7}
= 18

F cost (2 ,5) = min { 11+ cost (3,7), 8 + cost (3, 8) }
= min { 11 + 5 , 8+7}
= 15

F cost (1,1) = min { 9+ cost (2,2), 7 + cost (2, 3) , 3+ cost (2, 4), 2 + cost (2, 5) }
= min {9 +7 , 7+ 9 , 3 + 18, 2+ 15}
= 16

Algorithm F graph ( G, K, n, P ):

1. // The input is a k – stage graph G = (V, E ) with n vertices.
2. // indexed inorder of stages. E is a set of edges and C[ I , j].
3. // is the cost of < I , j >. P [1: K] is a minimum cost path.
4. {
5. cost [n] : 0.0;
6. For j : = n-1 to 1 step -1 do
7. { // compute cost [j]
8. Let r be a vertex such that < j , r > is an edge.
9. of G and C[j, r] + cost [r] is minimum ;
10. cost [j] : = c[j , r] + cost [r];
11. d[j] : = r;
12. }
13. // find a minimum cost path.
14. P[1] : = 1 ; P[k] : = n;
15. for j : = 2 to k-1 do P[j] : = d [P [j-1] ] ;
16. }

V1 V2 V3 V4 V5



b cost (3,6) = min {4+ b cost (2,2), 2 + b cost (2, 3) }
= min {4+ 9 , 2 +7}
= 9

b cost (3,7) = min {7+ b cost (2, 3), 11 + b cost (2, 5) }
= min {7+ 7 , 11 +2}
= 13

b cost (3,8) = min {1+ b cost (2,2), 11 + b cost (2, 4) + 8 + cost (2, 5) }
= min {1+ 9 , 11 +3, 8 + 2}
= 10

b cost (4,9) = min {6+ cost (3, 6), 4 + b cost (3, 7) }
= min {6+ 9 , 4 +13}
= 15

b cost (4, 10) = min {5+ cost (3, 6), 3 +cost (3, 7), 5 + cost (3, 8) }
= min {5+ 9 , 3 +13, 5+ 10}
= 14

b cost (4, 11) = min {6+ cost (3, 8)}
= min {6 + 10}
= 16

b cost (5, 12) = min {4+ cost (4, 9), 2 +cost (4, 10), 5 + cost (4, 11) }
= min {4+ 15 , 2 +14, 5+ 16}
= 16

Algorithm B Graph ( G, K, n, P):

1. // same function as F graph.
2. {
3. b cost [ 1] : = 0.0;
4. for j: = 2 to n do
5. { // compute b cost [j]
6. Let r be such that <r, j > is an edge of
7. G and bcost [r] + c[r, j] is minimum;
8. d[j]: = r;
9. }
10. // Find a minimum cost path.
11. P[1]: = 1 ; P[K] : = n;
12. for j: k-1 to 2 do P[j] : = d [P[j+1]];
13. }

Ans

Solution 3 is optimal. In this solution only jobs 1 and 4 are processed and the value is 17. These jobs must be processed in the order job 4 followed by job 1. Thus the processing of job 4 begins at time zero and that of job 1 is completed at time 2.

To formulate a greedy algorithm to obtain an optimal solution. We must formulate an optimization measure to determine how the next job is choosen. As a fist attempt we can choose the objective function ∑ i € j Pi as our optimization measure. Using this measure, the next job to include is the one that increases ∑ i € j Pi the most, subject to the constraint that the resulting J is a feasible solution. This requires us to consider jobs in non increasing order of the Pi’s = 0. Job 1 is added to J as it a feasible solution. Next, job 4 is considered. The solution J={1, 4} is also feasible. Next, job 3 is considered and discarded as J = { 1, 3, 4} is not feasible. Finally job 2 is considered. For inclusion into feasible. Hence, we are left with the solution J ={1, 4} with value 17. This is the optimal solution . For the given problem instance. The greedy algorithm just to this sequencing problem.

Ans:
G = (V,E) is an undirected graph.

S V such that E has atleast one vertex in S. S is the node cover of G.

We want to find whether there exists a graph G with node cover size k, for some k N.

The problem can be stated as:

NODE-COVER = {<G, K>|G has a node cover of size k}.

A deterministic algorithm to find a node cover in a graph is to list all subsets of nodes of size k & check each one to see whether it forms a node cover. This algorithm is exponential in k.

Next we show: The node cover problem is NP, i.e. Non-deterministic problem. Infact, we will show, it is NP-complete.

Given G = (V,E) we take S V & verify if it forms a node cover.

This can be done by checking for edge (u,v) E, whether u S or v S. This verification can be done in polynomial time.

Define the complement G’ = (V,E’), where E’ = {(u,v)|(u,v) E}.

G’ can be done in polynomial time. To convert G to G’, clique transformation is needed. This clique problem is NP-complete.

We show: this transformation is reduction. The graph has a clique of size k if G’ has a node cover of size |V| - k.

Suppose G has a clique S V with |S|=k.
We claim: V-S is a node cover in G’.

Let (u,v) be any edge in E’,
Then (u,v) E atleast one of u or v does not belong to S, since every pair of vertices in S is connected by an Edge of E.

Since (u,v) E’ is arbitrary, every edge of E’ is covered by a node in V-S.

V-S, which has size |V|-k forms a node cover for G’.

Conversely, Suppose G’ has a node cover S V, where |S| = V – k.

Then, for all u, v V, if (u,v) E’, then u S or V S or both. The contrapositive of this implication is that: for all u,v V, if u S & V S, then (u,v) E.

V-S is a clique, and it has size |V| - |S| = k.

The node-cover problem is NP-Complete.