
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) : BarNoy, 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