Re: [boost] BGL and hamiltonian paths

From: Douglas Paul Gregor (gregod_at_[hidden])
Date: 2002-08-16 10:43:41

On Fri, 16 Aug 2002, Fernando Cacciola wrote:
> > Probably *my* memory is failining me, but hamiltonian path is an
> NP-complete
> > problem. You can't solve it using any polynomial algorithm.
> >
> This is true for a general case.
> My case however, uses a complete graph of n vertices (Kn), that is, a graph
> in which every vertex is connected to all other vertices.
> All complete graphs are hamilton connected.
>
> Given that edges have weights, there should be a polynomial algorithm to
> find the minimum hamiltonian path in a weighted complete graph.

If that were true you could just take an arbitrary graph, add edges with
infinite weight to make it a complete graph, then you've got an algorithm
to find a hamiltonian path in polynomial time. (Or perhaps **my** memory
is failing me <g>)

        Doug