d*********w
发帖数: 5 | 1 I came across this tough algorithm problem and could not solve it. Wondering
if anyone knows the answer.
Either prove this problem is NP-complete or give a polynomial algorithm for
this problem.
Given a directed star graph, let the center be C and the other nodes
be N0, N1, N2, ..., NK. Each directed edge (C, Ni) or (Ni, C), 0<=i<=k,
is associated with a weight w(C, Ni) or w(Ni, C). Find a circle
N0'->N1'->N2'->...->Nk'->N0' (that covers all nodes N0, N1, ..., Nk)
such that the maximum distance |
|
