×

An algorithm to generate the ideals of a partial order. (English) Zbl 0608.90075

Generating the ideals of a partially ordered set is an important, frequently occurring problem in scheduling, reliability, sensitivity analysis for network flows and other combinatorial optimization problems. In this paper we present an algorithm which generates all the ideals of a partial order on n elements in O(n) time per ideal.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ball, M.O.; Provan, J.S., Calculating bounds on reachability and connectedness in stochastic networks, Networks, 13, 253-278, (1983) · Zbl 0569.68053
[2] Johnson, D.S.; Niemi, K.A., On knapsacks, partitions, and a new dynamic programming technique for trees, Math. oper. res., 8, 1-14, (1983) · Zbl 0506.90035
[3] Kao, E.P.C.; Queyranne, M., On dynamic programming methods for assembly line balancing, Oper. res., 30, 375-390, (1982) · Zbl 0481.90043
[4] Lawler, E.L., Efficient implementation of dynamic programming algorithms for sequencing problems, () · Zbl 0416.90036
[5] Möhring, R.H., Scheduling problems with a singular solution, Disc. appl. math., 16, 225-239, (1982) · Zbl 0489.90056
[6] Nemhauser, G.L.; Trotter, L.E., Vertex packings: structural properties and algorithms, Math. progr., 8, 232-248, (1975) · Zbl 0314.90059
[7] Picard, J.C.; Queyranne, M., On the structure of all minimum cuts in a network and applications, Math. progr. study, 13, 8-16, (1980) · Zbl 0442.90093
[8] Provan, J.S.; Ball, M.O., The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. comput., 12, 777-788, (1983) · Zbl 0524.68041
[9] Schrage, L.; Baker, K.R., Dynamic programming solution for sequencing problems with precedence constraints, Oper. res., 26, 444-449, (1978) · Zbl 0383.90054
[10] Steiner, G., Single machine scheduling with precedence constraints of dimension 2, Math. oper. res., 9, 248-259, (1984) · Zbl 0541.90054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.