Abstract
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 agree.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G.Behrendt (1988) Maximal antichains in partially ordered sets, Ars Combin. 25, no. C, 149–157.
GarrettBirkhoff (1948) Lattice Theory, American Math. Soc., Providence, RI.
G. Brightwell and P. Winkler (1990) Counting linear extensions is # P-complete, DIMACS TR 90-49.
Robert P. Dilworth (1958) Some Combinatorial Problems on Partially Ordered Sets, republished in [5] 13–18.
Robert P.Dilworth (1990) The Dilworth Theorems, Selected Papers of Robert P. Dilworth (1990) (Kenneth P.Bogard, RalphFreese, and Joseph P. S.Kung, eds), Birkhäuser Verlag, Boston, Basel, Berlin.
Stefan Felsner, Michel Habib, and Rolf H. Möhring (1991) On the Interplay between Interval Dimension and Dimension, Technische Universität Berlin 285/1991.
P. C.Fishburn (1985) Interval Orders and Interval Graphs, John Wiley & Sons, New York.
P.Grillet (1960) Maximal chains and antichains, Fund. Math. 65, 157–167.
MichelHabib and R.Jégou (1985) N-free posets as generalizations of series-parallel posets, Discrete Appl. Math. 12, no. 3, 279–291.
MichelHabib and Rolf H.Möhring (1987) On some complexity properties of N-free posets and posets with bounded decomposition diameter, Discrete Math. 63, 157–182.
MichelHabib, MichelMorvan, MauricePouzet, and Jean-XavierRampon (1991) Extension intervallaires minimalles, C.R. Acad. Sci. Paris 313, Série I, pp. 893–898.
B.Leclerc and B.Monjardet (1973) Orders “C.A.C.”, Fund. Math. 79, 11–22.
Gara Pruesse and Frank Ruskey (1991) Generating linear extensions fast, Tech. report, University of Toronto.
K. Reuter (1991) The jump number and the lattice of maximal antichains, Discrete Math.
IvanRival (1982) Optimal linear extensions by interchanging chains, Proc. Amer. Math. Soc. 89, 387–394.
Maciej M.Syslo (1982) A labeling algorithm to recognize a line graph and output its root graph, Inform. Process. Lett. 15, 28–30.
N.Wiener (1914) A contribution to the theory of relative position, Math. Proc. Cambridge Philos. Soc. 17, 441–449.
M.Yannakakis (1982) The complexity of the partial order dimension, SIAM J. Algebraic Discrete Methods 3, no. 3, 351–358.
Author information
Authors and Affiliations
Additional information
Communicated by I. Rival
This work was supported by the PROCOPE Program. The first author is supported by the DFG.
Rights and permissions
About this article
Cite this article
Gustedt, J., Morvan, M. N-free orders and minimal interval extensions. Order 9, 291–302 (1992). https://doi.org/10.1007/BF00383951
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00383951