How to keep a dynamic distributive directed graph acyclic and yet grant all requests of edge additions
Shimon Even, Y. B. Pnueli · 2002
A finite directed graph, G (V, E), is considered. The problem is to perform, online, a series of given requests to add or delete edges in the graph while keeping it acyclic. An algorithm that solves this problem is presented. The solution differs from that of S. Katz and O. Shmueli (1987) in that it has the following property. If every request to add an edge k to j is such that there is no path from j to k which persists forever, then every request to add an edge is eventually granted. The message complexity of the algorithm is O( mod E mod mod V mod ) messages per request.>