Finding Hamiltonian Path in Tournaments in O(nLogn)

Abhinav Rajesh Shripad

Explore an efficient algorithm for finding Hamiltonian Paths in Tournament graphs with a time complexity of O(n log n). We first prove the existence of Hamiltonian Paths in Tournaments and along the way find an O(n^2) algorithm for same. We then discuss the key insights and algorithms to achieve an O(n log n) time complexity. At the end we draw some parallels with the optimization techniques used with some very standard algorithms problem.

This is the third post of my new Astro blog.

This is the third post of my new Astro blog.