Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time

DOI10.1007/3-540-60084-1_71zbMath1412.68170OpenAlexW1632932043MaRDI QIDQ4645175

Mordechai M. Yung, John H. Reif, Paul G. Spirakis, Sotiris E. Nikoletseas

Publication date: 10 January 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60084-1_71

zbMATH Keywords

random graphneighborhood searchgiant componentdynamic algorithmconnectivity query

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• A topological approach to dynamic graph connectivity
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Expected parallel time and sequential space complexity of graph and digraph problems
• A data structure for dynamic trees
• Fully dynamic planarity testing with applications
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Linear expected-time algorithms for connectivity problems
• Fully Dynamic Algorithms for 2-Edge Connectivity
• On Finding and Updating Spanning Trees and Shortest Paths
• Expander properties in random regular graphs with edge faults
• Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item