1
$\begingroup$

I came across this problem whilst studying Gray codes during some current optimisation work. It seems likely to me that the complexity of it may be known. However, my background is not in computer science, so I'm not sure! I hope this is the correct forum.

Given an n-cube H, find an assignment of the set of all integers $\{0 : 2^n-1\}$ to the vertices of H, such that the sum of differences between pairs of integers at neighbouring vertices are minimised.

I have a reference which relates a similar instance to the TSP, but can't quite see if that is the case here as well.

Thanks in advance for any thoughts.

  • 0
    Absolute differences, yes.2012-03-01

0 Answers 0