Finding paths and deleting edges in directed acyclic graphs (Q1115184)

An algorithm for path searching and edge deleting in a directed acyclic graph is presented which realizes each searchpath operation in O(\(\ell)\) time, where \(\ell\) is the length of the achieved path, and any number of delete operations in O(mn) worst-case time, where m is the number of edges and n is the number of nodes. The algorithm requires a data structure of size \(O(n^ 2)\) which can be preprocessed in O(mn) time. This seems to improve previously known algorithms, which however handled the edge insertion problem also.