A polynomial algorithm for solving the “Hamiltonian circuit” problem is presented in the paper. Computational complexity of the algorithm is equal to , where n is the cardinality of the observed graph vertex set. Thus, the polynomial solvability for -complete problems is proved.
|ScienceOpen disciplines:||Computer science|
|Keywords:||Algorithm. Computational complexity. Hamiltonian cycle. Graph. NP-completeness|