New answers tagged dag
1
I do not know about their algorithm, but the problem is easy to solve in $\mathcal{O}(V \cdot e)$ time. The idea is to just do a DFS from every node to find vertices that can reach it. Normally this takes $\mathcal{O}(E)$ time, but we can use the irreducible kernel we have already built to do it in $\mathcal{O}(e)$ time.
First note that $e \geq n-1$ if the ...
5
Here is a dynamic programming algorithm. Given a graph $G = (V, E)$ and two vertices $u, v \in V$. We define the recursive function $C:V\rightarrow \mathbb{N}$, such that $C(w)$ is the number of paths from $w$ to $v$. Note that we are looking for the value of $C(u)$. We set $C(v) = 1$ and $C(w)=0$ for each vertex $w \neq v$ with out-degree equal to zeroo. ...
Top 50 recent answers are included
