I think there is a 4^k kernel for TSP ..
On Sat, Mar 14, 2009 at 4:49 PM, Miroslav Balaz wrote:
> I don't know any concrete real life problem, of course everyting real life
> problem that is in NP can be reducet to this problem.
> That includes timetable sheduling. | think there is no such proble
I don't know any concrete real life problem, of course everyting real life
problem that is in NP can be reducet to this problem.
That includes timetable sheduling. | think there is no such problem in
networks, because you need to know topology ad it has to be fixed. And if
you want to make multicas
I found a number of real life applications for the problem, like garbage
collection, a version of postman problem, gas system construction.. I am
looking for applications for the problem in networks, if any one can help.
On 3/14/09, Miroslav Balaz wrote:
>
>
> NP what?
> 2009/3/13 Amina Maarouf
NP complete, sorry
On 3/14/09, Miroslav Balaz wrote:
>
>
> NP what?
> 2009/3/13 Amina Maarouf
>
>> this problem was proved to be NP in a conference paper published recently.
>>
>>
>>
>> On Fri, Mar 13, 2009 at 10:44 AM, Miroslav Balaz > > wrote:
>>
>>> maybe you are not wrong. but with high prob