Re: Hamiltonian Cycles algorithm
- From: "Googmeister" <googmeister@xxxxxxxxx>
- Date: 18 Jan 2006 19:18:24 -0800
alex05 wrote:
> Does anyone know what the fastest algorithm is for finding if a graph
> has a hamiltonian cycle?
>
> I know it isn't efficient, but what is the current best we can do?
You can reduce HAM-CYCLE to TSP: set c(v, w) = 1
if v-w is an edge; and c(v, w) = 2 otherwise.
Then solve TSP with dynamic programming in O(n 2^n) time.
.
- References:
- Hamiltonian Cycles algorithm
- From: alex05
- Hamiltonian Cycles algorithm
- Prev by Date: Re: Hamiltonian Cycles algorithm
- Next by Date: Re: Is there an EXPSPACE complete language?
- Previous by thread: Re: Hamiltonian Cycles algorithm
- Next by thread: Finite function analysis and manipulation
- Index(es):
Relevant Pages
|
