PRIMALITY TESTING AND COUNTING THE NUMBER OF UNLABELED PRIME POSETS ON THIRTEEN ELEMENTS
S. M. Khamis; Khamis, Soheir;
Abstract
This 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 [3] 1997 are verified. A new number on n = 13 is computed.
Other data
Title | PRIMALITY TESTING AND COUNTING THE NUMBER OF UNLABELED PRIME POSETS ON THIRTEEN ELEMENTS | Authors | S. M. Khamis ; Khamis, Soheir | 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 |
Attached Files
File | Description | Size | Format | |
---|---|---|---|---|
PRIMALITY TESTING AND COUNTING THE NUMBER OF UNLABELED PRIME POSETS ON THIRTEEN ELEMENTS.pdf | 239.09 kB | Adobe PDF | View/Open |
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.