Quel est l'algorithme déterministe le plus rapide pour l'accessibilité au digraphe dynamique sans suppression de bord?

16

Quel est le meilleur résultat déterministe pour maintenir la fermeture transitive dynamique dans un graphique dirigé avec seulement une insertion de bord?

J'ai lu quelques articles sur le problème de fermeture transitive dynamique avec l'insertion et la suppression de bord. Cependant, existe-t-il de meilleurs algorithmes pour cela avec seulement une insertion de bord?

ds.algorithms graph-theory graph-algorithms dynamic-algorithms wei wang
la source
3
N'est-ce pas résolu par la structure de données union-find?
Tyson Williams
Votre graphique est-il dirigé ou non? @TysonWilliams a raison en ce que pour les graphiques non orientés sans suppression de bords, vous faites simplement une recherche d'union (chaque insertion est une opération UNION)
Suresh Venkat
1
Ah .. j'ai oublié de mentionner, c'est digraph. Ma mauvaise .... se mettra à jour alors.
wei wang

Réponses:

9

Un vieux document d'Italiano (GF Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48 (2–3): 273–281, 1986.) donne une structure de données qui prend en charge les insertions de bord en amorti requêtes de temps et d'accessibilité en temps constant. Je ne connais pas de meilleurs algorithmes incrémentaux.O(n)

virgi
la source