Fermeture transitive en ligne meilleure que O (N ^ 2) par addition de bord

Je recherche un algorithme en ligne pour maintenir la fermeture transitive d'un graphe acyclique dirigé avec une complexité temporelle inférieure à O (N ^ 2) par addition de bord. Mon algorithme actuel est comme ceci:

For every new edge u->v connect all nodes in Pred(u) \cup { u } with all nodes in Succ(v) \ \cup { v }.

Pour les bords O (N ^ 2), cela se traduit par une complexité temporelle totale de O (N ^ 4) bien pire que, par exemple, Floyd-Warshall .

ds.algorithms graph-theory ds.data-structures transitive-closure Alexandru
la source

Réponses:

O (n) temps par ajout de bord:

GF Italiano (1986): Amortized efficiency of a path retrieval data structure , Theoretical Computer Science 48, 273-281.
JA La Poutré et J. van Leeuwen (1988): Maintien des fermetures transitives et réductions transitives des graphiques , Proc. GT 1987 .

Jukka Suomela
la source

Voir aussi: DM Yellin. Accélérer la fermeture transitive dynamique pour les graphiques de degrés bornés. Acta Informatica, 30: 369–384, 1993.

Jeffε

Le premier article fournit deux opérations importantes à partir de la fermeture transitive, mais j'en ai besoin d'une troisième: itérer sur tous les nœuds accessibles. Le deuxième article est bon, cependant.

Alexandru