Recognizing Bellman–Ford-Orderable Graphs
Ramsey W. Haddad, Alejandro A. Schäffer · SIAM Journal on Discrete Mathematics · 1988
Mehlhorn and Schmidt [Discrete Appl. Math., 15 (1986), pp. 315–327 ] consider the following problem. Given a directed graph with distinguished source vertex s, is it possible to order the edges so that all simple paths starting at s use edges in increasing order? They show how to solve their problem in $O( | E |^2 )$ steps, where $| E |$ is the number of edges. An algorithm that runs in $O( | V |^2 )$ steps is given, where $| V |$ is the number of vertices. The new algorithm and its analysis apply and extend previous results on dominators in directed graphs.