http://heuristieken.nl/wiki/index.php?action=history&feed=atom&title=PPA_%26_Hard_Hamiltonian_Graphs 2026-04-17T21:43:20Z Revision history for this page on the wiki MediaWiki 1.30.0 http://heuristieken.nl/wiki/index.php?title=PPA_%26_Hard_Hamiltonian_Graphs&diff=2851&oldid=prev 2020-06-14T12:47:28Z

<p>‎<span dir="auto"><span class="autocomment">Errata</span></span></p> <table class="diff diff-contentalign-left" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr style="vertical-align: top;" lang="en"> <td colspan="2" style="background-color: white; color:black; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: white; color:black; text-align: center;">Revision as of 12:47, 14 June 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l10" >Line 10:</td> <td colspan="2" class="diff-lineno">Line 10:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">On the first page it says &quot;The hardest graphs reside in between, right around the Komlos-Szemeredi bound of average degreev·ln(v) +v·ln(ln(v)) edges&quot;. This is a mixeup. There&#160; are two possibilities:</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">1) The hardest graphs reside in between, right around the Komlos-Szemeredi bound of average degree ln(v) +ln(ln(v)).</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">2) The hardest graphs reside in between, right around the Komlos-Szemeredi bound of 1/2v·ln(v) + 1/2v·ln(ln(v)) edges.</ins></div></td></tr> </table>

MeesterDaan http://heuristieken.nl/wiki/index.php?title=PPA_%26_Hard_Hamiltonian_Graphs&diff=2848&oldid=prev 2020-05-13T21:08:36Z

<p></p> <table class="diff diff-contentalign-left" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr style="vertical-align: top;" lang="en"> <td colspan="2" style="background-color: white; color:black; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: white; color:black; text-align: center;">Revision as of 21:08, 13 May 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4" >Line 4:</td> <td colspan="2" class="diff-lineno">Line 4:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Here is our [http://heuristieken.nl/resources/(2020)Sleegers&amp;VandenBerg-PPAforhardHamiltoniangraphs.pdf paper].</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Here is our [http://heuristieken.nl/resources/(2020)Sleegers&amp;VandenBerg-PPAforhardHamiltoniangraphs.pdf paper].</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">==Errata==</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">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.</ins></div></td></tr> </table>

MeesterDaan http://heuristieken.nl/wiki/index.php?title=PPA_%26_Hard_Hamiltonian_Graphs&diff=2846&oldid=prev 2020-04-29T21:21:26Z

<p></p> <table class="diff diff-contentalign-left" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr style="vertical-align: top;" lang="en"> <td colspan="2" style="background-color: white; color:black; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: white; color:black; text-align: center;">Revision as of 21:21, 29 April 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l3" >Line 3:</td> <td colspan="2" class="diff-lineno">Line 3:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Paper==</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Paper==</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Here is our [http://heuristieken.nl/resources/(2020)Sleegers&amp;VandenBerg-PPAforhardHamiltoniangraphs paper].</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Here is our [http://heuristieken.nl/resources/(2020)Sleegers&amp;VandenBerg-PPAforhardHamiltoniangraphs<ins class="diffchange diffchange-inline">.pdf </ins>paper].</div></td></tr> </table>

MeesterDaan http://heuristieken.nl/wiki/index.php?title=PPA_%26_Hard_Hamiltonian_Graphs&diff=2845&oldid=prev 2020-04-29T21:21:03Z

<p></p> <table class="diff diff-contentalign-left" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr style="vertical-align: top;" lang="en"> <td colspan="2" style="background-color: white; color:black; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: white; color:black; text-align: center;">Revision as of 21:21, 29 April 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l3" >Line 3:</td> <td colspan="2" class="diff-lineno">Line 3:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Paper==</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Paper==</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Here is our [http://heuristieken.nl/resources/(2020)<del class="diffchange diffchange-inline">DeJonge</del>&amp;VandenBerg-<del class="diffchange diffchange-inline">PPAparameterization.pdf </del>paper].</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Here is our [http://heuristieken.nl/resources/(2020)<ins class="diffchange diffchange-inline">Sleegers</ins>&amp;VandenBerg-<ins class="diffchange diffchange-inline">PPAforhardHamiltoniangraphs </ins>paper].</div></td></tr> </table>

MeesterDaan http://heuristieken.nl/wiki/index.php?title=PPA_%26_Hard_Hamiltonian_Graphs&diff=2841&oldid=prev 2020-04-24T19:53:25Z

<p>Created page with &quot; ==Paper== Here is our [http://heuristieken.nl/resources/(2020)DeJonge&amp;VandenBerg-PPAparameterization.pdf paper].&quot;</p> <p><b>New page</b></p><div><br /> <br /> ==Paper==<br /> <br /> Here is our [http://heuristieken.nl/resources/(2020)DeJonge&amp;VandenBerg-PPAparameterization.pdf paper].</div>

MeesterDaan