Title
N-free Orders and Minimal Interval Extensions
Authors
-
Publication
ORDER, vol. 9, 1992, pp. 291-302
Source
-
Classification
-
not available
Keywords
-
not available
-
-
We investigate problems related to the set of minimal
interval extensions of N-free orders. This leads us
to a correspondence between this set for an arbitrary
order and a certain set of its maximal N-free
reductions. We also get a 1-1-correspondence
between the set of linear extensions of an arbitrary
order and the set of minimal interval extensions of the
linegraph of that order. This has an algorithmic
consequence, namely the problem of counting minimal
interval extensions of an N-free order is
#P-complete. Finally a characterization of all
N-free orders with isomorphic root graph is given in
terms of their lattice of maximal antichains; the
lattices are isomorphic iff the root graphs aggree.
