Re: [boost] BGL and hamiltonian paths

From: Greg Colvin (Gregory.Colvin_at_[hidden])
Date: 2002-08-16 10:09:04

At 08:47 AM 8/16/2002, you wrote:
>Fernando Cacciola wrote:
>
>> The problem (conceptually):
>>
>> Given a set of n geometric sites and a distance map with entries for each
>> pair of sites; that is, given a weighted Kn;
>> And given starting and ending sites (s,e).
>> I need to find the sequence of sites from the s to e that passes through
>> all the sites only once with the shortest step each; that is, I need to
>> find a minimum weight Hamiltonian path from s to e.
>>
>> I don't have any Graph book at hand, so if my memory isn't failing me, this
>> is essentially a matter of removing all but the lowest-weight out-edges
>> from s and e; and then removing all but the two lowest-weight out-edges
>> from all other vertices to form an euler graph, and finally doing a
>> topological sort.
>
>Probably *my* memory is failining me, but hamiltonian path is an NP-complete 
>problem. You can't solve it using any polynomial algorithm.

You can't solve it using any *known* polynomial algorithm ;->