Mining Posets from Linear Orders

Simple item page
dc.contributor.authorFernandez, Proceso L.en
dc.contributor.authorHeath, Lenwood S.en
dc.contributor.authorRamakrishnan, Narenen
dc.contributor.authorVergara, John Paul C.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:35:46Zen
dc.date.available2013-06-19T14:35:46Zen
dc.date.issued2009en
dc.description.abstractThere 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, several algorithms are presented for efficiently finding a single poset that generates the input set of linear orders. The variation of the problem where a minimum set of posets that cover the input is also explored. It is found that the problem is polynomially solvable for one class of simple posets (kite(2) posets) but NP-complete for a related class (hammock(2,2,2) posets).en
dc.format.mimetypeapplication/pdfen
dc.identifierhttp://eprints.cs.vt.edu/archive/00001083/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00001083/01/poset-paper-TR.pdfen
dc.identifier.trnumberTR-09-16en
dc.identifier.urihttp://hdl.handle.net/10919/20062en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectAlgorithmsen
dc.subjectData structuresen
dc.titleMining Posets from Linear Ordersen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
poset-paper-TR.pdf
Size:
198.7 KB
Format:
Adobe Portable Document Format
Download

Collections

Computer Science Technical Reports