A Logarithmic Time Sort for Linear Size Networks. Revised.

Abstract

We give a randomized algorithm that sorts on an N node network with constant valence in O(log N) time. More particularly the algorithm sorts N items on an N code cube-connected cycles graph and for some constant k for all large enough alpha it terminates within K alpha log N time with probability at least 1-n/alpha.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1982
Accession Number
ADA122659

Entities

People

  • John Reif
  • Leslie G. Valiant

Organizations

  • Harvard University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computations
  • Contracts
  • Diameters
  • Intervals
  • Military Research
  • Parallel Computing
  • Probability
  • Security
  • Sequences
  • Time Intervals
  • Trees (Data Structures)
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Regression Analysis.
  • Solar Physics