Suppose we have a weighted tournament graph. (A directed graph in which every pair of distinct vertices is connected by a single directed edge.)

The weights are constrained to be 0 and 1.

I know that every tournament contains atleast one hamiltonian path and can be found in time complexity $O(n^2)$.

However, I have two questions:

a) Is there a way to find the minimum weight hamiltonian path if we know that all weights are constrained to be either 0 or 1?

b) Is there an efficient algorithm to find ALL hamiltonian paths in a tournament graph?? This would solve a) automatically if true.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.