Extend reachability to total ordering
-
05-11-2019 - |
Question
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.
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange