Timeline for Orthogonal Hamiltonian cycles in (n x n x n) grids
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S May 16, 2021 at 14:26 | history | suggested | Matthieu Latapy |
added "lattices" and "graph-theory" tags
|
|
| May 16, 2021 at 11:54 | review | Suggested edits | |||
| S May 16, 2021 at 14:26 | |||||
| May 12, 2021 at 16:19 | answer | added | possiblywrong | timeline score: 8 | |
| May 9, 2021 at 10:42 | vote | accept | Joseph O'Rourke | ||
| May 8, 2021 at 23:26 | history | edited | Joseph O'Rourke | CC BY-SA 4.0 |
deleted 1 character in body
|
| May 8, 2021 at 23:10 | answer | added | Jukka Kohonen | timeline score: 5 | |
| May 8, 2021 at 22:25 | history | edited | Joseph O'Rourke | CC BY-SA 4.0 |
added 207 characters in body
|
| May 5, 2021 at 6:25 | comment | added | Jukka Kohonen | You could try small instances with a SAT solver. The standard reduction of Hamiltonian cycle to SAT has variables $x_{ij}$ encoding "the $i$th element of the cycle is vertex $j$", and appropriate constraints. It would seem straightforward to add constraints to enforce orthogonality, namely, after given two vertices you cannot next visit the third vertice that would continue the straight line. | |
| May 4, 2021 at 21:28 | comment | added | Joseph O'Rourke | @FrançoisBrunault: Good catch! Fixed now. | |
| May 4, 2021 at 21:28 | history | edited | Joseph O'Rourke | CC BY-SA 4.0 |
Fixed incorrect figure.
|
| May 4, 2021 at 20:34 | comment | added | François Brunault | Ah, but this is easily fixed by adding edges. | |
| May 4, 2021 at 20:26 | comment | added | François Brunault | It seems that 4 vertices are not visited in $C_4$, looking near two of the yellow sticks (or I need to change my glasses). | |
| May 4, 2021 at 14:27 | comment | added | Joseph O'Rourke | @FedorPetrov: Nice! Thanks. That settles Q1. | |
| May 4, 2021 at 13:45 | comment | added | Fedor Petrov | chess coloring proves that for odd $n$ there is no Hamiltonian cycle in $C_n$ (orthogonal or not) | |
| May 4, 2021 at 13:21 | history | asked | Joseph O'Rourke | CC BY-SA 4.0 |