|
Posa's Hamiltonian algorithm or any other algorithm
is at least exponential.
I read someone's blog doing this algorithm,
unfortunately, this is a typical exponential algorithm.
It's very easy to prove by dividing a constant saving
factor.
Posa's algorithm can only save a time factor of polynomial
degree one.
Even if you can save a time factor of high polynomial
degree, it is still exponential.
As its raw time complexity is n! / 2, in order to reduce
to polynomial, a reduction of exponential is the minimum,
for this purpose, you can not do anything for each possible
path or you need to reduce possible circles exponentially.
This is not possible.
Hope it can help get some ideas if you really do it.
Have a good time.
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-27 12:10
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社