most recent 30 from http://mathoverflow.net 2013-05-21T10:15:11Z http://mathoverflow.net/feeds/question/95472 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/95472/hamiltonian-paths-in-grid-graphs darryl 2012-04-28T23:45:04Z 2012-04-28T23:56:31Z

<p>I'm a non-mathematically inclined amateur whom is presently interested in Hamiltonian paths / Traveling Salesman problems.</p> <p>I would like to request that someone be kind enough to tell me whether my understanding of the following sentence found in this research paper (http://www.cs.technion.ac.il/~itai/publications/Algorithms/Hamilton-paths.pdf) is correct:</p> <p>"In contrast, the Hamilton path (and circuit) problem for general grid graphs is shown to be NP-complete"</p> <p>My understanding: <br/></p> <ul> <li>A grid graph is this type of graph: <a href="http://mathworld.wolfram.com/images/eps-gif/GridGraph_701.gif" rel="nofollow">http://mathworld.wolfram.com/images/eps-gif/GridGraph_701.gif</a></li> <li>NP-complete means if anyone can solve it, then a non general grid graph can be converted int o a general grid graph and be solved using the same algorithm.</li> <li>Traveling Salesman Problem is a Hamiltonian path (circuit) </li> </ul> <p>Additional questions:<br/></p> <ol> <li>Is the paper credible?</li> <li>What does the 'general' in 'general grid graph' mean?</li> </ol>

http://mathoverflow.net/questions/95472/hamiltonian-paths-in-grid-graphs/95473#95473 Igor Rivin 2012-04-28T23:56:31Z 2012-04-28T23:56:31Z

<ol> <li>It means that there are some grid graphs for which there is some simple algorithm (or simply an existence/nonexistence proof), but this cannot be done for an arbitrary grid graph.</li> </ol> <p>2.Traveling Salesman is not generally the same problem as hamiltonian path/circuit (usually there are costs involved).</p> <ol> <li><p>The paper is written by some of the best people in the field, and published in the best journal in the field.</p></li> <li><p>"General" means "arbitrary".</p></li> </ol>