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
3 votes
Accepted

Finding maximal elements of a partially ordered set

In the worst case, $\Theta(N^2)$ time can be required, for "unfriendly" partial orders. For some partial orders, faster algorithms will be possible, but to achieve better running time, the ...
D.W.'s user avatar
  • 162k

Top 50 recent answers are included