Skip to main content
MathOverflow

Return to Question

tags, mathjax, link
Source Link
Jukka Kohonen
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49

If you have a DAG, Gdirected acyclic graph (DAG) $G$, a topological sort is just an ordering of the vertices such that if an edge x->y$x \to y$ exists in G$G$, then the index of x$x$ is less than the index of y$y$.

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

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 efficiently can one compute the total number of topological sorts that exist for a given acyclic graph?

If you have a directed acyclic graph (DAG) $G$, a topological sort is just an ordering of the vertices such that if an edge $x \to 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 efficiently can one compute the total number of topological sorts that exist for a given acyclic graph?

fixed typo
Source Link
user5810
user5810

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 efficientefficiently can one compute the total number of topological sorts that exist for a given acyclic graph?

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?

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 efficiently can one compute the total number of topological sorts that exist for a given acyclic graph?

Source Link
haz
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?