“Testing Isomorphism and Recognition of N-free Posets”

Abstract

The 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).