Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
type: Item
instance of: scholarly article
title: Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
zbMATH Open document ID: 1412.68170
DOI: 10.1007/3-540-60084-1_71
published in: Automata, Languages and Programming
publication date: 2019-01-10T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q87
zbMATH DE Number: 6999429
zbMATH Keywords: random graph
zbMATH Keywords: neighborhood search
zbMATH Keywords: giant component
zbMATH Keywords: dynamic algorithm
zbMATH Keywords: connectivity query
author: Sotiris E. Nikoletseas
author: J. Reif
author: P. G. Spirakis
author: Moti Yung
MaRDI profile type: Publication
full work available at URL: 3-540-60084-1 71
OpenAlex ID: W1632932043
cites work: Q4886061
cites work: Fast probabilistic algorithms for Hamiltonian circuits and matchings
cites work: Q3138871
cites work: Q4230327
cites work: Q3286850
cites work: Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
cites work: Fully Dynamic Algorithms for 2-Edge Connectivity
cites work: Fully dynamic planarity testing with applications
cites work: Q4234100
cites work: Linear expected-time algorithms for connectivity problems
cites work: Expander properties in random regular graphs with edge faults
cites work: Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
cites work: A topological approach to dynamic graph connectivity
cites work: Expected parallel time and sequential space complexity of graph and digraph problems
cites work: A data structure for dynamic trees
cites work: Q3481743
cites work: On Finding and Updating Spanning Trees and Shortest Paths
Recommended article: Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time
Recommended article: Dynamic graph connectivity in polylogarithmic worst case time
Recommended article: Dynamic random networks and their graph limits
Recommended article: The Exponential Time Complexity of Computing the Probability That a Graph Is Connected
Recommended article: Acquaintance time of random graphs near connectivity threshold
Recommended article: Stochastic processes in random graphs
Recommended article: Cover Time in Edge-Uniform Stochastically-Evolving Graphs
Recommended article: Cover time in edge-uniform stochastically-evolving graphs
Recommended article: Approximating the Stochastic Network by its M Shortest Paths
Recommended article: Q4234100
description: scientific article; zbMATH DE number 6999429