Timeline for Finding a hamiltonianISH path in a graph
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 26, 2020 at 19:47 | comment | added | snowfrogdev | I'd also add that I am looking for an algorithm that will find ONE of the longest paths in a short amount of time, I don't care about absolutely getting THE longest path. An algorithm that might suit my need could potentially be quite different than the ones commonly used to solve the "longest path" or "hamiltonian path" problems. | |
| Mar 25, 2020 at 13:26 | comment | added | John Kemeny | The answer that the link in the comment refers to may give pointers, but your answer doesn't answer the question. The OP asks for longest path specifically in grid graphs, whereas you answer the question for general graphs. The answer in the link seems to be about Hamiltonian Path, not longest path. | |
| Mar 24, 2020 at 16:59 | comment | added | D.W.♦ | @PålGD, isn't this type of graph exactly the type that is covered by the NP-completeness result that Yuval Filmus links to? Am I missing something? Can you elaborate on where the room for hope lies? | |
| Mar 24, 2020 at 10:48 | comment | added | John Kemeny | Perhaps you can emphasize that this holds for general (and also planar and certain types of grid graphs)? I think you're presenting it as an all hope is lost scenario when that might not be the case. | |
| Mar 23, 2020 at 22:22 | comment | added | Yuval Filmus | Relevant: cs.stackexchange.com/a/12242/683. | |
| Mar 23, 2020 at 22:17 | history | undeleted | D.W.♦ | ||
| Mar 23, 2020 at 22:15 | history | deleted | D.W.♦ | via Vote | |
| Mar 23, 2020 at 22:15 | history | answered | D.W.♦ | CC BY-SA 4.0 |