TR88-01:
On the Comparison Cost of Partial Orders
Joseph C. Culberson and Gregory J. E. Rawlins
Date: February 1988
University of Alberta Technical Report TR88-01
Abstract
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.
Keywords: poset, partial order, sorting, lower bounds,
comparison based algorithms
Full Paper (postscript).
It can also
be retrieved (compressed postscript) by anonymous ftp
ftp.cs.ualberta.ca pub/TechReports
See also:
New Results from an Algorithm for Counting Posets
Joseph C. Culberson and Gregory J. E. Rawlins,
Order Vol. 7, 1991 pp 361-374
Queries: email joe@cs.ualberta.ca
or rawlins@moose.cs.indiana.edu
Joseph Culberson
April 20,1994