Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments

Abstract

We present a general method for translating sorting by comparisons algorithms to algorithms that compute a Hamilton path in a tournament. The translation is based on the relation between minimal feedback sets and Hamilton paths in tournaments. We prove that there is a one to one correspondence between the set of minimal feedback sets and the set of Hamilton paths. In the comparison model, all the tradeoffs for sorting between the number of processors and the number of rounds hold when a Hamilton path is computed. For the CRCW model, with O(n) processors, we show the following: (i) Two paths in a tournament can be merged in O(log log n) time (Valiant''s algorithm): (ii) a Hamilton path can be computed in O (log n) time (Cole''s algorithm). This improves a previous algorithm for computing a Hamilton path.