DIR Return Create A Forum - Home
       ---------------------------------------------------------
       knight tours
  HTML https://knighttours.createaforum.com
       ---------------------------------------------------------
       *****************************************************
   DIR Return to: general Hamiltonian cycles problem
       *****************************************************
       #Post#: 6--------------------------------------------------
       summary, review, keywords
       By: gsgs Date: March 4, 2023, 9:29 am
       ---------------------------------------------------------
       Still, the hardest graphs for all these depth-
       first based algorithms are found around the Komlós-
       Szemerédi bound, where the probability of a random
       graph being Hamiltonian goes from almost zero to al-
       most one as E increases (eqs.1 and 2).
       Interestingly enough though, all these are applied
       variations and subsets of just three optimization tech-
       niques: vertex degree preference, edge pruning, and
       non-Hamiltonicity checks.
       (Komlós and Szemerédi, 1983).
       Vacul’s algorithm
       Vacul’s algorithm is a depth-first search algorithm
       that uses pruning, non-Hamiltonicity checks and em-
       ploys a low-degree first ordering while recursing over
       the vertices.
       With the vertex set {1,2,…,n} and edges drawn independently with
       probability
       ( 1/2 *n*log(n) + 1/2 *n*log(log(n) + n*c_n) ) /  ( n*(n-1) / 2
       )
       for a real sequence (c_n) converging to c the probability of the
       event
       that the graph has a Hamiltonian cycle converges to the limit
       distribution
       exp(-exp(-c))
       1983. Limit distribution for the existence of hamiltonian cycles
       in a random graph
       János Komlós Endre Szemerédi
       P&a proved that a random graph with c*n*log(n) edges is
       Hamiltonian with probability tending
       to 1 if c >3.
       Korsunov improved this by showing that, if G_n is a random graph
       with
       1/2*n*log(n)n + 1/2*n*log(log(n)) + n*f(n) edges and f(n)
       towards infinity
       then G” is Hamiltonian, with probability tending to 1.
       We shall prove that if a graph G has n vertices and
       n log n + in log log n + cn
       edges, then it is Hamiltonian with probability PC tending to exp
       exp(-2)
       as n -+ 00.
       --------------------------------------------
       new method to create hard instances in 2020 :
  HTML https://www.researchgate.net/profile/Daan-Van-Den-Berg/publication/346824180_Looking_for_the_Hardest_Hamiltonian_Cycle_Problem_Instances/links/6025a82045851589399acc9c/Looking-for-the-Hardest-Hamiltonian-Cycle-Problem-Instances.pdf
       --------------------------------------------------------
       here a recent paper with a summary of the history of Hamilton
       cycle solvers
       and a new method,
       one part, RcerHAM , [1.2] is similar to the path-joining method
       4.)
       in the Warnsdorf-thread, but with subpath reversions =
       Posa-rotations
       at each step in the paths.
  HTML https://arxiv.org/pdf/2111.14771.pdf
       ===============================================
       *****************************************************