00000caa a22000003i 4500 UP-1685594773862388602 Buklod 20210322111246.0 m | | ta 210322s2018 xx r |||| u|eng d (iLib)UPBAG-00039569030 STII-DOST BAG rda eng ARTICLE-2787 Ordanel, Ivy D. author. Optimal deterministic algorithm for the hammock (2,2)-poset cover problem by Ivy D. Ordanel and Henry N. Adorna. 2018. pages 725-740 illustrations 26 cm text rdacontent unmediated rdamedia volume rdacarrier Includes bibliographical references (pages 739-740) The Poset Cover Problem is a hard optimization problem that has application to problems in data mining where the goal is to come up with directed acyclic networks that characterize the ordering pattern of a given set of sequential data. There have been variations to the problem, one of which is the Hammock( ð??? 2,2,...,2 )-Poset Cover Problem. It has been shown that the decision version of Hammock( ð??? 2,2,...,2 )-Poset Cover Problem is NP-complete when ð??? ≥ 3 but in ð??? when ð??? = 1, the complexity of the problem when ð??? = 2 was left open. In this study, we focus on the variation where ð??? = 2, that is the Hammock(2,2)-Poset Cover Problem, where the input is a collection of linear orders over a set and the output is a minimum set of Hammock(2,2)-Posets that covers or generates the given linear orders. We present an optimal deterministic algorithm for the problem that runs in ð???(ð???²ð???³ + ð???³ð???) where ð??? is the size of the set, ð??? is the number of linear orders, and ð??? is the number of all maximum matchings of a subgraph of the transposition graph of linear orders. We also present properties that show relationships of Hammock(2,2)- Poset Cover Problem to the Set Cover Problem, Cycle Cover Problem, and Edge Cover Problem. (Author's abstract). Computer science. Algorithm. Partial order. Poset. Adorna, Henry N. author. The Philippine Journal of Science Vol. 147, no. 4, December 2018. Request full-text access via UPB University Library through https://forms.gle/KZjBv7aRtY6jiL5E9 (viewed 22 March 2021) FI UPBAG UPBAG-MAIN ARTICLE-2787 Analytics