Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments,

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 15, 1988
Accession Number
ADA328575

Entities

People

  • Amotz Bar-noy
  • Joseph Naor

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Feedback
  • Mathematics
  • Notation
  • Numbers
  • Orientation (Direction)
  • Separators
  • Sequences
  • Square Roots
  • Theorems
  • Translations
  • Trees (Data Structures)
  • Universities

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.