P101: Enumeration of all topological sortings

P101: Enumeration of all topological sortings

Input:

A directed acyclic graph $D$.

Output:

All topological sortings $D$.

Complexity:

$O(1)$ amortized time per topological sorting and $O(|V|)$ space in addition to the space used for $D$.

Comment:

Linear sortings correspond to topological sortings.

Reference:

[Pruesse1994] (Bibtex)