An efficient algorithm for partial order production

We consider the problem of partial order production: arrange the elements of an unknown totally ordered set T into a target partially ordered set S, by comparing a minimum number of pairs in T. Special cases of this problem include sorting by comparisons, selection, multiple selection, and heap construction.

Authors

• Jean Cardinal
• Samuel Fiorini
• Gwenaël Joret
• Raphaël M. Jungers
• J. Ian Munro

Keywords

• graph entropy
• partial order