1,907

views

0

recommends

- Record: found
- Abstract: found
- Article: found

A polynomial algorithm for solving the “Hamiltonian circuit” problem is presented
in the paper. Computational complexity of the algorithm is equal to
$O\left({n}^{8}{\mathrm{log}}_{2}^{2}n\right)$
, where
*n* is the cardinality of the observed graph vertex set. Thus, the polynomial solvability
for
$\mathcal{N}P$
-complete problems is proved.

- Record: found
- Abstract: not found
- Article: not found

Mihalis Yannakakis (1991)

ScienceOpen

2199-1006

(ID: c0597241-52c2-47a7-8af0-dd09bbb57888
)

: 0

This work has been published open access under Creative Commons Attribution License
**
CC BY 4.0
**, which permits unrestricted use, distribution, and reproduction in any medium, provided
the original work is properly cited. Conditions, terms of use and publishing policy
can be found at
**
www.scienceopen.com
**.

Figures: 1,
Tables: 0,
References: 9,
Pages: 6

ScienceOpen disciplines: | Computer science |

Keywords: | Algorithm. Computational complexity. Hamiltonian cycle. Graph. NP-completeness |

Anatoly Panyukov wrote:

Indeed in the formula (4.3) should write V (G), and at the beginning of the 8-th row of section 5 should be "relaxed" instead of "elaxed". To encode the number $n=|V(G)| $ requires no more than $\log_2 n$ bits. Therefore, the complexity of computing the values of $M$, $\lambda^0$, and $R$ (see Proposition 8.3) does not exceed the value of the $O(log_2^2 n)$. Numerical experiment based on the subgradient algorithm for problem (6.3) was conducted. Assessment of its computational complexity above, but it allows you to use the 64 bit arithmetic for problems with n < 30.

2015-02-11 03:38 UTC