VTechWorks is currently accessible only on the VT network (campus, VPN). Elements deposit is now enabled. We are working to restore full access as soon as possible.
 

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