Amortized complexity of a transitive closure algorithm

Given a directed graph G, suppose that edges are added to or deleted from G, and it is required to compute its transitive closure in the on-line manner. This paper presents an efficient algorithm and analyzes its amortized running time by using Tarjan’s ‘potential’ technique. The result of the paper is as follows: the on-line computation of the transitive closureof G with n nodes, while m edges are added to and d edges are deleted from G, can be done in O((d+1)mn+(m-d)n) time if no cycle occurs in G. [In Japanese.]