An Efficient Algorithm for Decomposition of Partially Ordered Sets

Elsayed Badr, Mohamed EL-Hakeem, Enas E. El-Sharawy, Thowiba E. Ahmed and Mohammad W. Alomari

Journal of Mathematics, 2023, vol. 2023, 1-11

Abstract: 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.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/jmath/2023/9920700.pdf (application/pdf)
http://downloads.hindawi.com/journals/jmath/2023/9920700.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jjmath:9920700

DOI: 10.1155/2023/9920700

Access Statistics for this article

More articles in Journal of Mathematics from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().