{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:49:18Z","timestamp":1760240958098,"version":"build-2065373602"},"reference-count":12,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2019,10,19]],"date-time":"2019-10-19T00:00:00Z","timestamp":1571443200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100010892","name":"Department of Science and Technology, Republic of the Philippines","doi-asserted-by":"publisher","award":["NA"],"award-info":[{"award-number":["NA"]}],"id":[{"id":"10.13039\/501100010892","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Poset Cover Problem is an optimization problem where the goal is to determine a minimum set of posets that covers a given set of linear orders. This problem is relevant in the field of data mining, specifically in determining directed networks or models that explain the ordering of objects in a large sequential dataset. It is already known that the decision version of the problem is NP-Hard while its variation where the goal is to determine only a single poset that covers the input is in P. In this study, we investigate the variation, which we call the 2-Poset Cover Problem, where the goal is to determine two posets, if they exist, that cover the given linear orders. We derive properties on posets, which leads to an exact solution for the 2-Poset Cover Problem. Although the algorithm runs in exponential-time, it is still significantly faster than a brute-force solution. Moreover, we show that when the posets being considered are tree-posets, the running-time of the algorithm becomes polynomial, which proves that the more restricted variation, which we called the 2-Tree-Poset Cover Problem, is also in P.<\/jats:p>","DOI":"10.3390\/a12100219","type":"journal-article","created":{"date-parts":[[2019,10,21]],"date-time":"2019-10-21T03:40:29Z","timestamp":1571629229000},"page":"219","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Finding Two Posets that Cover Given Linear Orders"],"prefix":"10.3390","volume":"12","author":[{"given":"Ivy","family":"Ordanel","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of the Philippines Diliman, Quezon City 1101, Philippines"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"Jr.","given":"Proceso","family":"Fernandez","sequence":"additional","affiliation":[{"name":"Department of Information Sytems and Computer Science, Ateneo De Manila University, Quezon City 1108, Philippines"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henry","family":"Adorna","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of the Philippines Diliman, Quezon City 1101, Philippines"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,10,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1137\/S0097539791202647","article-title":"Generating linear extensions fast","volume":"23","author":"Pruesse","year":"1994","journal-title":"SIAM J. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0196-6774(83)90042-1","article-title":"On the generation of all topological sortings","volume":"4","author":"Kalvin","year":"1983","journal-title":"J. Algorithms"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"101","DOI":"10.4236\/ojdm.2013.33020","article-title":"The poset cover problem","volume":"3","author":"Heath","year":"2013","journal-title":"Open J. Discret. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2555","DOI":"10.1152\/jn.01030.2003","article-title":"A combinatorial method for analyzing sequential firing patterns involving an arbitrary number of neurons based on relative time order","volume":"92","author":"Lee","year":"2005","journal-title":"J. Neurophysiol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF02410536","article-title":"Process pathway via time series analysis","volume":"43","author":"Wiggins","year":"2003","journal-title":"Exp. Mech."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1145\/1233321.1233335","article-title":"Network reconstruction from dynamic data","volume":"8","author":"Unnikrishnan","year":"2006","journal-title":"ACM Sigkdd Explor. Newsl."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Puolam\u00e4ki, K., Fortelius, M., and Mannila, H. (2006). Seriation in paleontological data: Using markov chain monte carlo methods. PLoS Comput. Biol., 2.","DOI":"10.1371\/journal.pcbi.0020006"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/978-3-540-88411-8_4","article-title":"Finding total and partial orders from data for seriation","volume":"5255","author":"Mannila","year":"2008","journal-title":"Lect. Notes Comput. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1275","DOI":"10.1126\/science.277.5330.1275","article-title":"A test case of correlation metric construction of a reaction pathway from measurements","volume":"277","author":"Arkin","year":"1997","journal-title":"Science"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1350030","DOI":"10.1142\/S1793830913500304","article-title":"Mining posets from linear orders","volume":"5","author":"Fernandez","year":"2013","journal-title":"Discret. Math. Algorithms Appl."},{"key":"ref_11","first-page":"26","article-title":"Some heuristics for the 2-poset cover problem","volume":"9","author":"Sanchez","year":"2014","journal-title":"Philipp. Comput. J."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/0196-6774(92)90044-D","article-title":"Representing sets with constant time equality testing","volume":"13","author":"Yellin","year":"1992","journal-title":"J. Algorithms"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/219\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:27:49Z","timestamp":1760189269000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/219"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,19]]},"references-count":12,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2019,10]]}},"alternative-id":["a12100219"],"URL":"https:\/\/doi.org\/10.3390\/a12100219","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,10,19]]}}}