×

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

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
PDF BibTeX XML Cite
Full Text: DOI EuDML