wiki_research

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

hamiltonian_cycle_problem (657B)

      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 - even when the input is required to be a [bipartite_graph], or even a [grid_graph], cf [itai1982hamilton]
      7 
      8 [Approximation] algorithm: [christofides_heuristic]
      9 
     10 - [hamiltonian_cycle_cube] on [graph_cube]
     11 - [hamiltonian_cycle_square] on [graph_square]
     12 - [hamiltonian_cycle_multiple] going multiple times over each [vertex]
     13 
     14 Special case: [Knight's_tour]
     15 
     16 Up: [computational_problem], [hamiltonian_cycle]
     17 
     18 See also: [Hamiltonian_path_problem]