1
$\begingroup$

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.

$\endgroup$

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.