Priority Queues and Permutations

Michael David Atkinson, R Beals

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

A priority queue transforms an input permutation a of some set of size n into an output permutation tau. The set R(n) of such related pairs (sigma, tau) is studied. Efficient algorithms for determining s(tau) = \sigma : (sigma,tau) epsilon R(n)/ and t (sigma) = \tau : (sigma,tau) epsilon R(n)\ are given, a new proof that \R(n)\ = (n + 1)(n-1) is given, and the transitive closure of R(n) is found.

Original languageEnglish
Pages (from-to)1225-1230
Number of pages6
JournalSIAM Journal on Computing
Volume23
Issue number6
DOIs
Publication statusPublished - Dec 1994

Keywords

  • PRIORITY QUEUE
  • PERMUTATION
  • ENUMERATION

Fingerprint

Dive into the research topics of 'Priority Queues and Permutations'. Together they form a unique fingerprint.

Cite this