On minimizing the jump number for interval orders

In ``the greedy poset problem one seeks to determine those finite posets P whose greedy linear extensions are jump-optimal as well. The Rival-Zaguia 1983 result to the effect that the sets of greedy linear extensions and jump-optimal linear extensions are identical for N-free posets is probably the best known result along these lines to date. This paper is another installment illustrating the R-Z approach as applied to a particular and important class of posets, viz., the interval posets. An important 1986 result of Rival-Zaguia characterizes general greedy posets in a somewhat complicated way. By transformation-refinement of the arguments needed to obtain this result (Thm. 1 in the present paper) and some useful specific lemmas, the authors demonstrate in the proof of Theorem 2 that an interval poset P is greedy if and only if every N in P is completed from above or below. Here \(N=\{a,b,c,d|\) \(a<c\), \(b<c\), \(b<d\}\) is ``completed from below if (1) a has at least one lower cover, (2) for every x covered by a, the order on \(\{\) x,a,b,c,d\(\}\) is such that \(x<d\) (in P), (3) whenever x is covered by a and t covers x, \(t\neq a\), then \(t>b.\) The terminology ``completed from above has an obvious dual meaning. Using Theorem 2 one obtains a computationally effective means of solving the greedy poset problem for interval orders. The problem is known to be NP-hard otherwise.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: On minimizing the jump number for interval orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111581)