Impact
~3k
people reached
- 0 posts edited
- 0 helpful flags
- 0 votes cast
Nov
11 |
awarded | Notable Question |
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? |