AVERAGE CASE ANALYSIS OF FULLY DYNAMIC REACHABILITY FOR DIRECTED GRAPHS

摘要

On considère le problème de préserver la fermeture transitive d'un graphe orienté pendant l'insertion et l'élimination d'arêtes du point de vue de l'analyse du cas moyen. Soit n le nombre de sommets et m le nombre d'arêtes. Nous introduisons une structure de donnée qui permet de supporter soit la recherche d'un chemin ente deux sommets en temps moyen O (n · log n) et en temps O (1) pour chaque mise à jour dans le cas pire, soit de requette concernent l'existence d'un chemin entre deux sommets en temps moyen O ( 1 ) et en temps moyen amorti pour chaque mise à jour. Les bornes précédentes deviennent O (1) et O (log~3 n) respectivement dans le cas où m > n_(4/3). Les bornes obtenues sont meilleures vis-à-vis des bornes qu'on obtient dans l'analyse du pire cas. Enfin on considère un modèle d'analyse au milieu entre l'analyse du cas moyen et l'analyse du pire cas : l'adversaire « semi-random » introduit en [3).%We consider the problem of maintaining the transitive closure in a directed 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 path between two nodes in O (n · log n) expected time and O (1) worst case time per update, and reachability queries in O (1) expected time and 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 (log~3 n) expected amortized time per update. These bounds compare favorably with the best bounds known using worst case analysis. Furthermore we consider an intermediate model between worst case analysis and average case analysis: the semi-random adversary introduced in [3].