Accession Number : ADA328575

Title :   Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Bar-Noy, Amotz ; Naor, Joseph

PDF Url : ADA328575

Report Date : 15 DEC 1988

Pagination or Media Count : 25

Abstract : We present a general method for translating sorting by comparisons 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: (1) Two paths in a tournament can be merged in O(log log n) time (Valiant's algorithm Va); (2) a Hamilton path can be computed in O(log n) time (Cole's algorithm). This improves a previous algorithm for computing a Hamilton path.

Descriptors :   *ALGORITHMS, *GAME THEORY, MATHEMATICAL MODELS, OPTIMIZATION, PARALLEL PROCESSING, CONTROL SEQUENCES.

Subject Categories : Operations Research
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE