Online-Transitivschluss besser als O (N ^ 2) pro Kantenaddition

Ich suche nach einem Online-Algorithmus, um den transitiven Abschluss eines gerichteten azyklischen Graphen mit einer Zeitkomplexität von weniger als O (N ^ 2) pro Kantenaddition aufrechtzuerhalten. Mein aktueller Algorithmus sieht folgendermaßen aus:

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

Für O (N ^ 2) -Kanten bedeutet dies eine Gesamtzeitkomplexität von O (N ^ 4), die viel schlimmer ist als beispielsweise Floyd-Warshall .

ds.algorithms graph-theory ds.data-structures transitive-closure Alexandru
quelle

Antworten:

O (n) Zeit pro Kantenaddition:

GF Italiano (1986): Amortisierte Effizienz einer Pfadabrufdatenstruktur , Theoretical Computer Science 48, 273–281.
JA La Poutré und J. van Leeuwen (1988): Aufrechterhaltung transitiver Abschlüsse und transitiver Reduktionen von Graphen , Proc. WG 1987 .

Jukka Suomela
quelle

Siehe auch: DM Yellin. Beschleunigung des dynamischen transitiven Schließens für Graphen mit begrenzten Graden. Acta Informatica, 30: 369–384, 1993.

Jeffs

Der erste Artikel enthält zwei wichtige Operationen aus dem transitiven Schließen, aber ich brauche eine dritte: das Durchlaufen aller zugänglichen Knoten. Das zweite Papier ist jedoch gut.

Alexandru