“Testing Isomorphism and Recognition of N-free Posets”

Bayoumi I. Bayoumi, ; Khamis, Soheir 


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

Other data

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

CORE Recommender

Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.