AVERAGE-CASE ANALYSIS OF FULLY DYNAMIC REACHABILITY FOR DIRECTED-GRAPHS

We consider the problem of maintaining the transitive closure in a dir ected graph under edge insertions and deletions from the point of view of average case analysis. Say n the number of nodes and m the number of edges. We present a data structure that supports the report of a pa th between two nodes in O (n . log n) expected time and O (1) worst ca se time per update, and reachability queries in O (1) expected time an d O (n . log n) expected amortized time per update. If m > n(4/3) then reachability queries can be performed in O (1) expected time and O (l og(3) n) expected amortized time per update. These bounds compare favo rably with the best bounds known using worst case analysis. Furthermor e we consider an intermediate model between worst case analysis and av erage case analysis: the semi-random adversary introduced in [3].