Procesco L. Fernandez, Lenwood Heath, Naren Ramakrishnan, Michael Tan, John Paul Vergara

Abstract

There has been much research on the combinatorial problem of generating the linear extensions of a given poset. This paper focuses on the reverse of that problem, where the input is a set of linear orders, and the goal is to construct a poset or set of posets that generates the input. Such a problem finds applications in computational neuroscience, systems biology, paleontology, and physical plant engineering. In this paper, two algorithms are presented for efficiently finding a single poset, if, such a poset exists whose linear extensions are exactly the same as the input set of linear orders. The variation of the problem where a minimum set of posets that cover the input is also explored. This variation is shown to be polynomially solvable for one class of simple posets (kite(2) posets) but NP-complete for a related class (hammock(2,2,2) posets).

People

Heath-updated

Lenwood Heath


Ramakrishnan-updated

Naren Ramakrishnan


Publication Details

Date of publication:
October 10, 2013
Journal:
Algorithms and Applications
Volume:
5
Issue Number:
4