An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms

DOI10.1145/945394.945398MaRDI QIDQ5463421zbMATH OpenOpenAlexFDO

Authors Raj D. Jun. Iyer, Hariharan S. Rahul, Mikkel Thorup, David R. Karger

Publication date 4 August 2005

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL http://www.jea.acm.org/2001/IyerConnectivity/

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
• Algorithmic aspects in speech recognition
• Near-optimal fully-dynamic graph connectivity
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• scientific article; zbMATH DE number 1775391

Cited in

(3)

• Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study
• Fast compatibility testing for rooted phylogenetic trees
• Maintaining dynamic minimum spanning trees: an experimental study

This page was built for publication: An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5463421)