1
$\begingroup$

Given a finite DAG $G = (V, E)$ with $|E| \in \mathcal{O}(|V|)$, I want to compute a total ordering $<$ over $V$ that is compatible to reachability: If there is a transition $(u, v) \in E$, then $u < v$.

The only way I could think of was to use Floyd-Warshall to compute a reachability matrix and then somehow extend that to be total. This would require cubic time, which is too slow for my needs. I require a quadratic time algorithm at most. In a publication I read that this is actually possible in linear time but no procedure or further explanation was provided.

$\endgroup$
2
$\begingroup$

You can compute a topological ordering of the vertices in linear time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.