PRIMALITY TESTING AND COUNTING THE NUMBER OF UNLABELED PRIME POSETS ON THIRTEEN ELEMENTSS. M. Khamis ; Khamis, Soheir
AbstractThis paper gives a new polynomial algorithm for testing whether or not a given poset, P , is prime. The basic idea of the given algorithm depends on finding a proper autonomous set of elements of P. The algorithm decides that P is prime if each pair of elements of P does not belong to a proper autonomous set. Via this test, unlabeled prime posets on n elements are counted. The strategy of the suggested counting algorithm is: (1) Create an upper triangular matrix satisfying the bucket form; (2) Apply the primality test to accept a constructed matrix if it corresponds to a prime poset; and (3) Compute the weight of the accepted matrix of enumeration. The three steps are repeated to obtain the sum of the weights of all upper triangular matrices with bucket form that correspond to prime posets. In constructing these matrices, we follow a colexecographic (colex.) order w.r.t. rows. As a result, the previously known numbers of such posets on n 12 recorded in  1997 are verified. A new number on n = 13 is computed.
|Keywords||Counting, enumerating, partially ordered sets, finite poset, unlabeled, prime, and algorithm.||Issue Date||1997||Conference||The International Conference on Mathematics Trends and Developments, Egyptian Mathematical Society||URI||http://research.asu.edu.eg/123456789/1129|
Recommend this item
|PRIMALITY TESTING AND COUNTING THE NUMBER OF UNLABELED PRIME POSETS ON THIRTEEN ELEMENTS.pdf||239.09 kB||Adobe PDF||View/Open|
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.