Compatibility between interval structures and partial orderings. If H=(X,E) is a hypergraph, n the cardinality of X,In the ordered set {1..n} and < an order relation on X, we call F(X,<) the set of the one-to-one functions from X to In which are compatible with <. If A In we denote by (A) the length of the smallest interval of In which contains A. We first deal with the following problem: Find ƒ F(X,<) which minimise
. The ae, e R are positive coefficients. This problem can be understood as a scheduling problem and is checked to be NP-complete. We learn how to recognize in polynomial time those hypergraphs H=(X,E) which induce an optimal value of z min equal to
. Next we work on a dual question which arises about interval graphs, when some partial orderings on the vertex set of these graphs intend to represent inclusion, overlapping or anteriority relations between closed intervals of the real line. |