AbstractThe main results of this paper are two algorithms applied on the class of N-free posets . The first one is a linear-time algorithm to recognize whether or not a poset is an N-free one. This method depends on checking a well-known structural property of the N-free posets, then constructing block and matrix representations in case of the N-free poset. The second algorithm is a fixed time algorithm for testing isomorphism of N-free posets. The isomorphism problem for N-free posets can be transformed to test whether or not the matrix representations of the given posets are identical under certain accepted permutations on rows and columns. This can be done in a time of O(k2.k!), where k (bounded) is the order of a matrix. For N-free interval posets, this problem can be easily solved in O(k2).
|Keywords||: Poset , N-free poset , interval order , complexity , testing isomorphism .||Issue Date||1996||Journal||Congresses Numeratium||URI||http://research.asu.edu.eg/123456789/1138|
Recommend this item
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.