Parameterized Algorithm for the Poset Cover Problem

• Main Authors: Ordanel, Ivy D., Fernandez, Proceso L., Juayong, Richelle Ann B., Clemente, Jhoirene B., Adorna, Henry N.
• Format: text
• Published: Archīum Ateneo 2024
• Subjects: linear orders; parameterized algorithm; poset; XP; Mathematics; Physical Sciences and Mathematics
• Online Access: https://archium.ateneo.edu/discs-faculty-pubs/410; https://archium.ateneo.edu/context/discs-faculty-pubs/article/1410/viewcontent/parameterized_algorithm_for_the_Poset_cover_problem_.pdf
• Institution: Ateneo De Manila University

It is already known that the 1-Poset and 2-Poset Cover Problems are in P. In this paper, we extended the previous results and devised an algorithm for the k-Poset Cover Problem, for any k number of posets that cover the input. The algorithm runs in O(m2k n2), where m and n are the input size. With t...