1
$\begingroup$

Question:

have there been serious attempts to design divide and conquer heuristics for generating near optimal Hamilton Cycles in complete symmetric graphs?


For clarification:

by a divide and conquer heuristic for TSP I mean

  • recursively partitioning the set of vertices with minimal size difference (i.e. equal for even size and difference 1 for odd sizes),
    create at most two TSP from the partions until the instances can be optimally solved
  • repeatedly creating a graph with a small number of Hamilton Cycles, e.g. a ladder graph, from the tours through both parts and return the Hamilton Cycle with optimal length.
$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.