Technical Report 550-1997

Title

Weak-Order Extensions of an Order

Authors

Karell Bertet, Jens Gustedt, and Michel Morvan

Publication

Appeared in Graph-Theoretic Concepts of Computer Science, WG'97, Rolf H. Möhring (Ed.), Lecture Notes in Computer Science 1335, p. 65-77

Source

Download as [ps.gz]

Classification

not available

Keywords

not available

Abstract

In this paper, at first we describe a graph representing all the weak-order extensions of a partially ordered set and an algorithm generating them. Then we present a graph representing all of the minimal weak-order extensions of a partially ordered set, and implying a generation algorithm. Finally, we prove that the number of weak-order extensions of a partially ordered set is a comparability invariant, whereas the number of minimal weak-order extensions of a partially ordered set is not a comparability invariant.