wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

hamiltonian_cycle_problem (550B)

      1 # Hamiltonian cycle problem
      2 
      3 The [decision_problem] of whether an input [undirected_graph] admits a [Hamiltonian_cycle], or the [function_problem] of finding one
      4 
      5 It is [NP_hard], like the [Hamiltonian_path_problem]
      6 
      7 [Approximation] algorithm: [christofides_heuristic]
      8 
      9 - [hamiltonian_cycle_cube] on [graph_cube]
     10 - [hamiltonian_cycle_square] on [graph_square]
     11 - [hamiltonian_cycle_multiple] going multiple times over each [vertex]
     12 
     13 Special case: [Knight's_tour]
     14 
     15 Up: [computational_problem], [hamiltonian_cycle]
     16 
     17 See also: [Hamiltonian_path_problem]