Re: [boost] BGL and hamiltonian paths

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2002-08-16 12:50:45

----- Original Message -----
From: "Douglas Paul Gregor" <gregod_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Friday, August 16, 2002 12:43 PM
Subject: Re: [boost] BGL and hamiltonian paths

> 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>)
>
Well, I don't want to go off topic here, but I'm not convinced (yet :-)), so
I'll move this to sci.math (you are welcome to meet me there).

Anyway, I asked here in order to know if the BGL supported this in any
specific way, which I now know it doesn't.

Thanks,

Fernando Cacciola
Sierra s.r.l.
fcacciola_at_[hidden]
www.gosierra.com