Greedy linear extensions with constraints

✍ Scribed by Ivan Rival; Nejib Zaguia

• Publisher: Elsevier Science
• Year: 1987
• Tongue: English
• Weight: 762 KB
• Volume: 63
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(87)90014-8

✦ Synopsis

Loosely speaking, a greedy linear extension of an ordered set is a linear extension obtained by following the rule: "climb as high as you can". Given an ordered set P and a partial extension P' of P is there a greedy linear extension of P which satisfies all of the inequalities of P'? We consider special instances of this question. In particular, we impose conditions bearing on the diagg;pm of an ordered set. Our results have applications, to the 'jump number scheduling problem' and to the 'greedy dimension'.