Skip to main content

New answers tagged

3 votes

Random directed acyclic graph (Barak-Erdös): find "upstream" vertices

This answer draws heavily from D.W.'s, which got the ball rolling. The algorithm ...
UJM's user avatar
  • 73
2 votes

Random directed acyclic graph (Barak-Erdös): find "upstream" vertices

I will assume you mean $p$ to be a fixed constant, and you care about the asymptotics as $N \to \infty$. In this case, for each fixed $p$ with $0<p<1$, I believe there is an $\tilde{O}(N)$ time ...
D.W.'s user avatar
  • 162k

Top 50 recent answers are included