Abstrakt. Vi presenterar en algoritm för riktade acykliska grafer som bryter igenom O(n 2 ) barriären på enkeloperation komplexiteten av helt dynamisk transitiv stängning, där n är antalet kanter i grafen. Vi kan svara på frågor i O(n ) värsta fall-tid och utföra uppdateringar i O(n) (1,,1)- +n 1+ ) värsta fall-tid, för alla  till [0, 1], där  ska (1,, 1) är exponenten för multiplikation av en n × n-matris med en n × n-matris. De nuvarande bästa gränserna på  ska (1,, 1) innebär en O (n 0.575 ) frågestund och en O (n 1.575 ) uppdateringstid i värsta fall. Vår subquadratiska algoritm är randomiserad och har ett ensidigt fel. Som en tillämpning av detta resultat visar vi hur man löser single-source räckvidd i O(n 1.575 ) tid per uppdatering och konstant tid per fråga.
En annan Monte Carlo algoritm av Demeterscu och Italiano REF minskade uppdateringstiden till O(n 1.575 ) även i värsta fall, men på bekostnad av en O(n 0.575 ) värsta fall frågetid.
Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O(n2 barrier
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}