From Daan
MeesterDaan (talk | contribs) |
MeesterDaan (talk | contribs) (→Errata) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 4: | Line 4: | ||
Here is our [http://heuristieken.nl/resources/(2020)Sleegers&VandenBerg-PPAforhardHamiltoniangraphs.pdf paper]. | Here is our [http://heuristieken.nl/resources/(2020)Sleegers&VandenBerg-PPAforhardHamiltoniangraphs.pdf paper]. | ||
| + | |||
| + | |||
| + | |||
| + | ==Errata== | ||
| + | |||
| + | The title of the paper is somewhat misleading; we're actually no looking for hard Hamiltonian graphs, but hard Hamiltonian problem instances, and the result of that are actually non-Hamiltonian graphs only. | ||
| + | |||
| + | |||
| + | On the first page it says "The hardest graphs reside in between, right around the Komlos-Szemeredi bound of average degreev·ln(v) +v·ln(ln(v)) edges". This is a mixeup. There are two possibilities: | ||
| + | |||
| + | |||
| + | 1) The hardest graphs reside in between, right around the Komlos-Szemeredi bound of average degree ln(v) +ln(ln(v)). | ||
| + | |||
| + | 2) The hardest graphs reside in between, right around the Komlos-Szemeredi bound of 1/2v·ln(v) + 1/2v·ln(ln(v)) edges. | ||
Latest revision as of 12:47, 14 June 2020
Paper
Here is our paper.
Errata
The title of the paper is somewhat misleading; we're actually no looking for hard Hamiltonian graphs, but hard Hamiltonian problem instances, and the result of that are actually non-Hamiltonian graphs only.
On the first page it says "The hardest graphs reside in between, right around the Komlos-Szemeredi bound of average degreev·ln(v) +v·ln(ln(v)) edges". This is a mixeup. There are two possibilities:
1) The hardest graphs reside in between, right around the Komlos-Szemeredi bound of average degree ln(v) +ln(ln(v)).
2) The hardest graphs reside in between, right around the Komlos-Szemeredi bound of 1/2v·ln(v) + 1/2v·ln(ln(v)) edges.