2 replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
source | link

If the original value of count is 1 in every node, then this is the problem of counting the number of successors of each node in a dag. That problem is discussed in http://cstheory.stackexchange.com/q/553/5038https://cstheory.stackexchange.com/q/553/5038, which cites the best algorithms known for this problem. For sparse graphs, it is hard to do much better than running DFS separately from each vertex, which has running time approximately $O(VE)$. For dense graphs, you can build an algorithm whose running time is $O(V^\omega)$, where $\omega$ is the exponent for fast matrix multiplication ($\omega \approx 2.8$ in practice).

If the original value of the counts can be different from 1, then your problem is http://cstheory.stackexchange.com/q/736/5038https://cstheory.stackexchange.com/q/736/5038, which discusses the best running times known, and even mentions an approximation algorithm you could consider.

If the original value of count is 1 in every node, then this is the problem of counting the number of successors of each node in a dag. That problem is discussed in http://cstheory.stackexchange.com/q/553/5038, which cites the best algorithms known for this problem. For sparse graphs, it is hard to do much better than running DFS separately from each vertex, which has running time approximately $O(VE)$. For dense graphs, you can build an algorithm whose running time is $O(V^\omega)$, where $\omega$ is the exponent for fast matrix multiplication ($\omega \approx 2.8$ in practice).

If the original value of the counts can be different from 1, then your problem is http://cstheory.stackexchange.com/q/736/5038, which discusses the best running times known, and even mentions an approximation algorithm you could consider.

If the original value of count is 1 in every node, then this is the problem of counting the number of successors of each node in a dag. That problem is discussed in https://cstheory.stackexchange.com/q/553/5038, which cites the best algorithms known for this problem. For sparse graphs, it is hard to do much better than running DFS separately from each vertex, which has running time approximately $O(VE)$. For dense graphs, you can build an algorithm whose running time is $O(V^\omega)$, where $\omega$ is the exponent for fast matrix multiplication ($\omega \approx 2.8$ in practice).

If the original value of the counts can be different from 1, then your problem is https://cstheory.stackexchange.com/q/736/5038, which discusses the best running times known, and even mentions an approximation algorithm you could consider.

1
source | link

If the original value of count is 1 in every node, then this is the problem of counting the number of successors of each node in a dag. That problem is discussed in http://cstheory.stackexchange.com/q/553/5038, which cites the best algorithms known for this problem. For sparse graphs, it is hard to do much better than running DFS separately from each vertex, which has running time approximately $O(VE)$. For dense graphs, you can build an algorithm whose running time is $O(V^\omega)$, where $\omega$ is the exponent for fast matrix multiplication ($\omega \approx 2.8$ in practice).

If the original value of the counts can be different from 1, then your problem is http://cstheory.stackexchange.com/q/736/5038, which discusses the best running times known, and even mentions an approximation algorithm you could consider.