On the number of linear extensions in a precedence graph
J.M. Miller, George C. Stockman · 2002
An algorithm that acts as an oracle by estimating the number of sequential orders possible for a set of tasks and precedence constraints is presented. The basic oracle algorithm always completes in low order polynomial time even when there are an exponential number of orders, and it produces an exact answer for graphs with simple folds. The algorithm is applicable to many practical problems in CAPP and should be of value in searching for efficient sequences of operations.>