Open Access. Powered by Scholars. Published by Universities.®
Databases and Information Systems Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
Articles 1 - 2 of 2
Full-Text Articles in Databases and Information Systems
Approximation And Computational Complexity Of Some Hammock Variations Of The Poset Cover Problem, Ivy Ordanel, Proceso L. Fernandez Jr, Richelle Ann B. Juayong, Henry N. Adorna
Approximation And Computational Complexity Of Some Hammock Variations Of The Poset Cover Problem, Ivy Ordanel, Proceso L. Fernandez Jr, Richelle Ann B. Juayong, Henry N. Adorna
Department of Information Systems & Computer Science Faculty Publications
The Hammock(⏟𝟐, 𝟐 , … , 𝟐 / 𝒌 )-Poset Cover Problem is a variation of the Poset Cover Problem with the same input – set {𝑳𝟏, 𝑳𝟐, … , 𝑳𝒎} of linear orders over the set {𝟏, 𝟐, … ,𝒏}, but the solution is restricted to a set of simple hammock(𝟐⏟, 𝟐 , … , 𝟐 / 𝒌 ) posets. The problem is NP-Hard when 𝒌 ≥ 𝟑 but is in 𝑷 when 𝒌 = 𝟏. The computational complexity of the problem when 𝒌 = 𝟐 is not yet known. In this paper, …
On Finding Two Posets That Cover Given Linear Orders, Ivy Ordanel, Proceso L. Fernandez Jr, Henry Adorna
On Finding Two Posets That Cover Given Linear Orders, Ivy Ordanel, Proceso L. Fernandez Jr, Henry Adorna
Department of Information Systems & Computer Science Faculty Publications
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 …