Re: Hamiltonian Cycles algorithm

In article <1137536900.654177.172520@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
alex05 <alexmcferron@xxxxxxxxx> wrote:
>Does anyone know what the fastest algorithm is for finding if a graph
>has a hamiltonian cycle?

One relevant reference is a 1995 paper by Alon, Yuster, and Zwick entitled
"Color-coding." I think their method yields an algorithm that runs in
time 2^n * m * log n for a graph with m edges and n vertices. I don't
know if this is the best known, though. In general the search keyword
you want is "exact algorithm."
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.