Home > Fully dynamic biconnectivity and transitive closure > HTML MARC |

000099332 001__ 99332 000099332 005__ 20190101013027.0 000099332 037__ $$aCONF 000099332 245__ $$aFully dynamic biconnectivity and transitive closure 000099332 260__ $$c1995 000099332 269__ $$a1995 000099332 336__ $$aConference Papers 000099332 520__ $$aThis paper presents an algorithm for the fully dynamic biconnectivity problem whose running time is exponentially faster than all previously known solutions. It is the first dynamic algorithm that answers biconnectivity queries in time O(pow2(log(n)) in a n-node graph and can be updated after an edge insertion or deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized algorithm with the update time amortized update time O(pow(log(n),4)). Only recently the best deterministic result for this problem was improved to Osqrt(n.pow2(log(n))). We also give the first fully dynamic and a novel deletions-only transitive closure (i.e. directed connectivity) algorithms. These are randomized Monte Carlo algorithms. Let n be the number of nodes in the graph and let M be the average number of edges in the graph during the whole update sequence: The fully dynamic algorithms achieve (1) query time O(n/logn) and update time O(M.sqrt(n.pow2(log(n)))+n); or (2) query time O(n/logn) and update time O[pow(M,(u-1)/u))].pow2(log(n))=O[M.pow(n,0.58).pow2(log(n))], where u is the exponent for boolean matrix multiplication (currently u=2.38). The deletions-only algorithm answers queries in time O(n/logn). Its amortized update time is O(n.pow2(log(n))) 000099332 6531_ $$aalgorithm theory 000099332 6531_ $$acomputational complexity 000099332 6531_ $$agraph theory 000099332 6531_ $$arandomised algorithms 000099332 6531_ $$aLas-Vegas style 000099332 6531_ $$adeletion 000099332 6531_ $$adynamic algorithm 000099332 6531_ $$aedge insertion 000099332 6531_ $$afully dynamic biconnectivity 000099332 6531_ $$an-node graph 000099332 6531_ $$apolylogarithmic time 000099332 6531_ $$arandomized algorithm 000099332 6531_ $$atransitive closure 000099332 700__ $$0243545$$aHenzinger, Monika R.$$g165464 000099332 700__ $$aKing, Valerie 000099332 773__ $$q664-672$$tFoundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on 000099332 8564_ $$zURL 000099332 8564_ $$s1086841$$uhttps://infoscience.epfl.ch/record/99332/files/HenzingerHK95.pdf$$zn/a 000099332 909C0 $$0252227$$pLTAA$$xU11062 000099332 909CO $$ooai:infoscience.tind.io:99332$$pconf$$qGLOBAL_SET 000099332 937__ $$aLTAA-CONF-1995-002 000099332 970__ $$aHenzinger1995/LTAA 000099332 973__ $$aOTHER$$rREVIEWED$$sPUBLISHED 000099332 980__ $$aCONF