ERA

Download the full-sized PDF of On the Comparison Cost of Partial OrdersDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R30Q7R

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

On the Comparison Cost of Partial Orders Open Access

Descriptions

Author or creator
Culberson, Joseph
Rawlins, Gregory
Additional contributors
Subject/Keyword
comparison based algorithms
lower bounds
poset
sorting
partial order
Type of item
Report
Language
English
Place
Time
Description
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.
Date created
1988
DOI
doi:10.7939/R30Q7R
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-30T22:28:48.439+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 853043
Last modified: 2015:10:12 12:44:52-06:00
Filename: TR88-01.pdf
Original checksum: daedbe0dd9f2c175712d3fc15a4a3192
Well formed: true
Valid: true
Page count: 23
Activity of users you follow
User Activity Date