On the Comparison Cost of Partial Orders

• Author(s) / Creator(s)

  • Culberson, Joseph
  • Rawlins, Gregory

• Technical report TR88-01. A great deal of effort has been directed towards determining the minimum number of binary comparisons sufficient to produce various partial orders given some partial order. For example, the sorting problem considers the minimum number of comparisons sufficient to construct a total order starting from n elements. The merging problem considers the minimum number of comparisons sufficient to construct a total order from two total orders. The searching problem can be seen as a special case of the merging problem in which one of the total orders is a singleton. The selection problem considers the minimum number of comparisons sufficient to select the ith largest of n elements. Little, however, is known about the minimum number of comparisons sufficient to produce an arbitrary partial order. In this paper we briefly survey the known results on this problem and we present some first results on partial orders which can be produced using either restricted types of comparisons or a limited number of comparisons. | TRID-ID TR88-01

• Date created

  1988

• Subjects / Keywords

  • Poset
  • Lower bounds
  • Comparison based algorithms
  • Sorting
  • Partial order

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R30Q7R

• License

  Attribution 3.0 International