Calcul des idéaux d’un ordonné fini. (Calculus of ideals of finite posets). (French) Zbl 0733.90038

Bordat, J.-P.

RAIRO, Rech. Opér. 25, No. 3, 265-275 (1991).

Summary: The ideals of a finite poset P and their lattice structure provide a useful tool for several problems in scheduling, network flows, and other poset problems. We present an algorithm which generates these idals in O(w(P)) time per ideal, where w(P) is the width of P. The distributive lattice may be generated in the same complexity.

MSC:

90B35	Deterministic scheduling theory in operations research
90C48	Programming in abstract spaces
06B10	Lattice ideals, congruence relations
90C35	Programming involving graphs or networks
90C60	Abstract computational complexity for mathematical programming problems
06D99	Distributive lattices
90B10	Deterministic network models in operations research

Keywords:

ideals of a finite poset; lattice structure