Daniele

Unregistered less info
31 reputation
2
bio website
location
age
visits member for 4 years, 5 months
seen Apr 2 '10 at 11:48

Mar
8
awarded  Popular Question
Mar
31
comment Is this a well known NP-complete problem?
Yes, but this way you are setting $v$ and $w$. While the problem is to find any path of length $n$, without choosing any $v$ or $w$.
Mar
31
comment Is this a well known NP-complete problem?
Thanks for your answer. However, how do you find the minimal weight path of length $n$ in $H$? Hasn't the same problem just shifted to $H$?
Mar
31
awarded  Student
Mar
31
comment Is this a well known NP-complete problem?
A path can visit the same node more than once yes. By shortest I meant least weight. By length I meant the number of edges. I think Francois was kind enough to correct the question that now should be clearer. Andrew you are absolutely right that it should be stated as a decision problem. Actually, knowing whether the decision problem lies in NP solve my problem.
Mar
31
comment Is this a well known NP-complete problem?
Yes it refers to the sum of the weights of the edges on the path of length 'n'. Sorry if that was not clear.
Mar
31
asked Is this a well known NP-complete problem?