Recognition of prime posets and one of its applicationsKhamis, Soheir
AbstractThe paper contains a recognition algorithmic method for deciding whether a given poset, P, is prime. The algorithm is designed to determine whether there exists a proper P-autonomous set including specified two distinct elements of P. The steps are repeated for all ordered pairs of distinct elements of P, if it is prime, in a polynomial time. As an application of this test, the author counted the number of unlabeled prime posets regarding heights up to 13 elements. The height counting algorithm depends on: (1) Create the colexecographic list of all strictly upper triangular matrices satisfying the bucket from; (2) Apply the given test to choose those corresponding to prime posets; and (3) Enumerate the required number regarding height by summing the weights of accepted matrices, that are also computed in the algorithm. The algorithm added to height counting field, the original numbers of unlabeled 13-element prime posets of height k; k · 13, and verified the previously known numbers of unlabeled n-element prime posets of height k; 1 · k · n · 12, that have been introduced in .
|Keywords||Counting, enumeration, partially ordered sets, finite poset, unlabeled, prime, height, and algorithm||Issue Date||2006||Journal||JOURNAL OF THE EGYPTIAN MATHEMATICAL SOCIETY||URI||http://research.asu.edu.eg/123456789/1132|
Recommend this item
|Recognition of prime posets and one of its applications.pdf||119.71 kB||Adobe PDF||View/Open|
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.