wiki_research

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

edge_hamiltonian_path_problem (407B)

      1 # Edge hamiltonian path problem
      2 
      3 The [computational_problem] of [deciding], given an [undirected_graph], whether it admits a [line_graph_hamiltonian_path], i.e., whether its [line_graph] has a [hamiltonian_path]
      4 
      5 It is [NP_complete] by [lai1993edge] already on [bipartite_graphs]
      6 
      7 Up: [decision_problem], [line_graph_hamiltonian_path]
      8 
      9 See also: [edge_hamiltonian_cycle_problem], [hamiltonian_path_problem]