An Efficient Algorithm for Decomposition of Partially Ordered Sets
Efficient time complexities for partial ordered sets or posets are well-researched field. Hopcroft and Karp introduced an algorithm that solves the minimal chain decomposition in O (n2.5) time. Felsner et al. proposed an algorithm that reduces the time complexity to O (kn2) such that n is the number...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2023-01-01
|
| Series: | Journal of Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2023/9920700 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849693018302447616 |
|---|---|
| author | Elsayed Badr Mohamed EL-Hakeem Enas E. El-Sharawy Thowiba E. Ahmed |
| author_facet | Elsayed Badr Mohamed EL-Hakeem Enas E. El-Sharawy Thowiba E. Ahmed |
| author_sort | Elsayed Badr |
| collection | DOAJ |
| description | Efficient time complexities for partial ordered sets or posets are well-researched field. Hopcroft and Karp introduced an algorithm that solves the minimal chain decomposition in O (n2.5) time. Felsner et al. proposed an algorithm that reduces the time complexity to O (kn2) such that n is the number of elements of the poset and k is its width. The main goal of this paper is proposing an efficient algorithm to compute the width of a given partially ordered set P according to Dilworth’s theorem. It is an efficient and simple algorithm. The time complexity of this algorithm is O (kn), such that n is the number of elements of the partially ordered set P and k is the width of P. The computational results show that the proposed algorithm outperforms other related algorithms. |
| format | Article |
| id | doaj-art-95df26883c014707b0c445d2d2b6982b |
| institution | DOAJ |
| issn | 2314-4785 |
| language | English |
| publishDate | 2023-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Mathematics |
| spelling | doaj-art-95df26883c014707b0c445d2d2b6982b2025-08-20T03:20:33ZengWileyJournal of Mathematics2314-47852023-01-01202310.1155/2023/9920700An Efficient Algorithm for Decomposition of Partially Ordered SetsElsayed Badr0Mohamed EL-Hakeem1Enas E. El-Sharawy2Thowiba E. Ahmed3Scientific Computing DepartmentArtificial Intelligence DepartmentComputer Science DepartmentComputer Science DepartmentEfficient time complexities for partial ordered sets or posets are well-researched field. Hopcroft and Karp introduced an algorithm that solves the minimal chain decomposition in O (n2.5) time. Felsner et al. proposed an algorithm that reduces the time complexity to O (kn2) such that n is the number of elements of the poset and k is its width. The main goal of this paper is proposing an efficient algorithm to compute the width of a given partially ordered set P according to Dilworth’s theorem. It is an efficient and simple algorithm. The time complexity of this algorithm is O (kn), such that n is the number of elements of the partially ordered set P and k is the width of P. The computational results show that the proposed algorithm outperforms other related algorithms.http://dx.doi.org/10.1155/2023/9920700 |
| spellingShingle | Elsayed Badr Mohamed EL-Hakeem Enas E. El-Sharawy Thowiba E. Ahmed An Efficient Algorithm for Decomposition of Partially Ordered Sets Journal of Mathematics |
| title | An Efficient Algorithm for Decomposition of Partially Ordered Sets |
| title_full | An Efficient Algorithm for Decomposition of Partially Ordered Sets |
| title_fullStr | An Efficient Algorithm for Decomposition of Partially Ordered Sets |
| title_full_unstemmed | An Efficient Algorithm for Decomposition of Partially Ordered Sets |
| title_short | An Efficient Algorithm for Decomposition of Partially Ordered Sets |
| title_sort | efficient algorithm for decomposition of partially ordered sets |
| url | http://dx.doi.org/10.1155/2023/9920700 |
| work_keys_str_mv | AT elsayedbadr anefficientalgorithmfordecompositionofpartiallyorderedsets AT mohamedelhakeem anefficientalgorithmfordecompositionofpartiallyorderedsets AT enaseelsharawy anefficientalgorithmfordecompositionofpartiallyorderedsets AT thowibaeahmed anefficientalgorithmfordecompositionofpartiallyorderedsets AT elsayedbadr efficientalgorithmfordecompositionofpartiallyorderedsets AT mohamedelhakeem efficientalgorithmfordecompositionofpartiallyorderedsets AT enaseelsharawy efficientalgorithmfordecompositionofpartiallyorderedsets AT thowibaeahmed efficientalgorithmfordecompositionofpartiallyorderedsets |