We present an algorithm for directed acyclic graphs that breaks through the O(n^2) barrier on the single-operation complexity of fully dynamic transitive closure, where n is the number of edges in the graph. We can answer queries in O(n^?) worst-case time and perform updates in O(n^{?(1,?,1)??}+n^{1+?}) worst-case time, for any ? in [0,1], where ?(1,?,1) is the exponent of the multiplication of an n × n^? matrix by an n^? × n matrix. The current best bounds on ?(1,?,1) imply an O(n^0.575) query time and an O(n^1.575) update time in the worst case. Our subquadratic algorithm is randomized, and has one-sided error. As an application of this result, we show how to solve single-source reachability in O(n^1.575) time per update and constant time per query.
Trade-Offs for Fully Dynamic Reachability on DAGs: Breaking Through the O(n^2) Barrier / Demetrescu, Camil; Italiano, G. F.. - In: JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY. - ISSN 0004-5411. - STAMPA. - 52(2):(2005), pp. 147-156. [10.1145/1059513.1059514]
Trade-Offs for Fully Dynamic Reachability on DAGs: Breaking Through the O(n^2) Barrier
DEMETRESCU, Camil;
2005
Abstract
We present an algorithm for directed acyclic graphs that breaks through the O(n^2) barrier on the single-operation complexity of fully dynamic transitive closure, where n is the number of edges in the graph. We can answer queries in O(n^?) worst-case time and perform updates in O(n^{?(1,?,1)??}+n^{1+?}) worst-case time, for any ? in [0,1], where ?(1,?,1) is the exponent of the multiplication of an n × n^? matrix by an n^? × n matrix. The current best bounds on ?(1,?,1) imply an O(n^0.575) query time and an O(n^1.575) update time in the worst case. Our subquadratic algorithm is randomized, and has one-sided error. As an application of this result, we show how to solve single-source reachability in O(n^1.575) time per update and constant time per query.File | Dimensione | Formato | |
---|---|---|---|
VE_2005_11573-129778.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
102.89 kB
Formato
Adobe PDF
|
102.89 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.