{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T13:49:59Z","timestamp":1773150599254,"version":"3.50.1"},"reference-count":21,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>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).<\/jats:p>","DOI":"10.1142\/s1793830913500304","type":"journal-article","created":{"date-parts":[[2013,9,3]],"date-time":"2013-09-03T02:10:16Z","timestamp":1378174216000},"page":"1350030","source":"Crossref","is-referenced-by-count":5,"title":["MINING POSETS FROM LINEAR ORDERS"],"prefix":"10.1142","volume":"05","author":[{"given":"PROCESO L.","family":"FERNANDEZ","sequence":"first","affiliation":[{"name":"Department of Information Systems and Computer Science, Ateneo de Manila University, Quezon City 1108, Philippines"}]},{"given":"LENWOOD S.","family":"HEATH","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Virginia Tech, Blacksburg VA 24061, USA"}]},{"given":"NAREN","family":"RAMAKRISHNAN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Virginia Tech, Blacksburg VA 24061, USA"}]},{"given":"MICHAEL","family":"TAN","sequence":"additional","affiliation":[{"name":"Department of Information Systems and Computer Science, Ateneo de Manila University, Quezon City 1108, Philippines"}]},{"given":"JOHN PAUL C.","family":"VERGARA","sequence":"additional","affiliation":[{"name":"Department of Information Systems and Computer Science, Ateneo de Manila University, Quezon City 1108, Philippines"}]}],"member":"219","published-online":{"date-parts":[[2013,12,3]]},"reference":[{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1126\/science.277.5330.1275"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-3165(96)80001-X"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF00383444"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01108590"},{"key":"rf9","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001"},{"key":"rf10","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1145\/545151.545174","volume":"45","author":"Fayyad U. M.","journal-title":"Commun. ACM"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"rf15","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1145\/545151.545179","volume":"45","author":"Han J.","journal-title":"Commun. ACM"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2007.07.084"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016548222238"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.181"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1152\/jn.01030.2003"},{"key":"rf26","doi-asserted-by":"crossref","first-page":"1467","DOI":"10.1109\/TKDE.2006.172","volume":"18","author":"Pei J.","journal-title":"IEEE Tran. on Knowl. and Data Eng."},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762129"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1137\/0404037"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791202647"},{"key":"rf30","first-page":"62","volume":"2","author":"Puolamaki K.","journal-title":"PLoS Computat. Biol."},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90067-8"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1007\/BF02410536"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1137\/0603036"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.125"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830913500304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,5]],"date-time":"2022-03-05T11:32:54Z","timestamp":1646479974000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830913500304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":21,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2013,12,3]]},"published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1142\/S1793830913500304"],"URL":"https:\/\/doi.org\/10.1142\/s1793830913500304","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]}}}