Is there a polynomial algorithm to solve TSP (or Ham Cycle) on an m by n solid grid graph whose points are at unit distance apart? I've heard about Umans and Lenhart research paper but reading such paper is beyond my capability.

  • 2
    $\begingroup$ What problem do you want to solve on solid grid graphs ? Hamiltonian Cycle ? $\endgroup$ – Shiva Kintali Mar 30 '12 at 10:30
  • $\begingroup$ @Shiva, Yes, Hamiltonian Cycle, Travelling Salesman. $\endgroup$ – user8925 Mar 30 '12 at 11:29
  • 5
    $\begingroup$ Could you please edit the question (and the title)? $\endgroup$ – Jeffε Mar 30 '12 at 11:47
  • $\begingroup$ What is “m by n solid grid graph”? If it means the m×n grid graph with mn vertices, then it is straightforward to see that the Hamiltonian Cycle problem on such graphs is in P. $\endgroup$ – Tsuyoshi Ito Mar 30 '12 at 16:28
  • $\begingroup$ even if it's beyond you to read the paper, doesn't the abstract answer your question? computer.org/portal/web/csdl/doi/10.1109/SFCS.1997.646138 $\endgroup$ – Sasho Nikolov Mar 30 '12 at 20:00

This paper is more general than what you're asking for, but should lead you to some answers. It's pretty accessible too:


(Though looking at it now the primary reference I'd have suggested out of that would be the Umans and Lenhart paper...)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.