P348: Enumeration of all topological sortings in a directed acyclic graph

P348: Enumeration of all topological sortings in a directed acyclic graph

Input:

A directed graph $G$.

Output:

All topological sortings in $G$.

Complexity:

$O(1)$ amortized time per solution with $O(|G|)$.

Comment:

Linear extensions correspond to topological sortings.

Reference:

[Pruesse1991a] (Bibtex)