Approximation and Computational Complexity of Some Hammock Variations of the Poset Cover Problem

• Main Authors: Ordanel, Ivy, Fernandez, Proceso L, Jr, Juayong, Richelle Ann B, Adorna, Henry N
• 格式: text
• 出版: Archīum Ateneo 2020
• 主題: algorithm; approximation; complexity; partial order; poset; Computer Sciences; Databases and Information Systems; Mathematics
• 在線閱讀: https://archium.ateneo.edu/discs-faculty-pubs/280; https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1275&context=discs-faculty-pubs
• 機構: Ateneo De Manila University

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 ≥ bu...