Skip to main content
1 of 3
haz
  • 231
  • 2
  • 5

How can you compute the number of topological sorts in a DAG?

If you have a DAG, G, a topological sort is just an ordering of the vertices such that if an edge x->y exists in G, then the index of x is less than the index of y.

It's not hard to figure out how a topological sort can be given, but how efficient can one compute the total number of topological sorts that exist for a given acyclic graph?

haz
  • 231
  • 2
  • 5