On the generation of all topological sortings

Abstract

Three algorithms that generate all topological sortings of a partially ordered finite set are discussed and compared. A substantially improved version of Wells' algorithm is presented, and this is shown to be similar to, but less efficient than the Knuth-Szwarcfiter algorithm. A third algorithm given by Varol and Rotem is shown to be still more efficient. The dependence of this latter algorithm on the particular choice of starting solution is analyzed, and a heuristic for choosing a starting solution that minimizes cost is proposed. © 1983.