Timeline for NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 31, 2018 at 0:01 | history | tweeted | twitter.com/StackCSTheory/status/1035316694825295875 | ||
| Aug 26, 2018 at 15:06 | vote | accept | Elle Najt | ||
| Aug 26, 2018 at 8:49 | answer | added | Gamow | timeline score: 8 | |
| Aug 26, 2018 at 4:33 | comment | added | Mikhail Rudoy | The degree of a vertex of G* corresponds to the number of edges in a face of G. So a simpler way of asking your question is to ask about the Hamiltonian cycle problem in planar graphs with an upper bound on the number of edges in each face. As a separate note, reducing from grid-graph Hamiltonian cycle is probably a good idea if you want to end up with each face having a small number of edges. | |
| Aug 26, 2018 at 1:56 | history | asked | Elle Najt | CC BY-SA 4.0 |