Back to Search
Start Over
Parameterized Algorithm for the Poset Cover Problem.
- Source :
-
Philippine Journal of Science . Feb2024, Vol. 153 Issue 1, p23-32. 10p. - Publication Year :
- 2024
-
Abstract
- It is already known that the 1-Poset and 2-Poset Cover Problems are in 𝑷. In this paper, we extended the previous results and devised an algorithm for the 𝒌-Poset Cover Problem, for any 𝒌 number of posets that cover the input. The algorithm runs in 𝑶(𝒎2k 𝒏2), where 𝒎 and 𝒏 are the input size. With this running time, we can say that the problem belongs to XP (slicewise polynomial). The algorithm runs efficiently for small fixed 𝒌 but runs exponentially for large 𝒌. While the algorithm running time has yet not to be efficient for large 𝒌, we have shown a significant improvement from a brute-force solution, which runs in 2𝒎 𝒏2 + 𝑶(􀷌𝒌 𝒊 􀰸 1 2𝒎𝒊𝒏) - exponential even for small fixed [ABSTRACT FROM AUTHOR]
- Subjects :
- *PARTIALLY ordered sets
Subjects
Details
- Language :
- English
- ISSN :
- 00317683
- Volume :
- 153
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Philippine Journal of Science
- Publication Type :
- Academic Journal
- Accession number :
- 177056860