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
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 probability you are wrong. In
>> general case, this problem cannot ba approxi
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 probability you are wrong. In
> general case, this problem cannot ba approximated for any polynomialy
> computable function
maybe you are not wrong. but with high probability you are wrong. In
general case, this problem cannot ba approximated for any polynomialy
computable function f.
You can tell me the algorithm
or give me reason why trirvial reduction from TSP does not work here?
2009/3/13 Ajinkya Kale
> If i am
If i am not wrong there is a parameterized algorithm for this which is in P
On Fri, Mar 13, 2009 at 3:40 AM, Miroslav Balaz wrote:
> Ok this is NP-comlete... so no fast algorithm is known
>
> 2009/3/12 Amina Maarouf
>
> Dear All;
>>
>> I need some help on the following problem:
>>
>> Giv
Ok this is NP-comlete... so no fast algorithm is known
2009/3/12 Amina Maarouf
> Dear All;
>
> I need some help on the following problem:
>
> Given a weighted graph ( v, e) and a set of marked vertices v' subset to v
> and a source node n. Find a cycle to that visits all vertices in v' a
