Efficiently find maximum XOR on a graph

Revision en1, by shubhinanugullu, 2016-11-13 09:59:37

We are given an undirected graph G = (V, E), |V| ≤ 50. We are also given a starting vertex s. Each vertex v of the graph is associated with a natural number Nv. Initiall our profit is R = Ns.

Now we have to traverse the graph beginning from s in an order. We can visit each vertex or edge an number of times.Whenever we reach a vertex v, R = R XOR Nv. (Note that if we visit a vertex v k times, then we will XOR with Nv k times.

Find the maximum value of R that can be obtained while traversing G.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English shubhinanugullu 2016-11-13 09:59:37 580 Initial revision (published)