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


Conference Paper

© Springer-Verlag Berlin Heidelberg 1995. This paper introduces average case analysis of fully dynamic graph connectivity (when the operations are edge insertions and deletions). To this end we introduce the model of stochastic graph processes, i.e. dynamically changing random graphs with random equiprobable edge insertions and deletions, which generalizes Erdös and Renyi’s 35 year-old random graph process. As the stochastic graph process continues indefinitely, all potential edge locations (in V × V) may be repeatedly inspected (and learned) by the algorithm. This learning of the structure seems to imply that traditional random graph analysis methods cannot be employed (since an observed edge is not a random event anymore). However, we show that a small (logarithmic) number of dynamic random updates are enough to allow our algorithm to re-examine edges as if they were random with respect to certain events (i.e. the graph “forgets” its structure). This short memory property of the stochastic graph process enables us to present an algorithm for graph connectivity which admits an amortized expected cost of O(log3 n) time per update. In contrast, the best known deterministic worst-case algorithms for fully dynamic connectivity require n1/2 time per update.

Full Text

Duke Authors

Cited Authors

  • Nikoletseas, S; Reif, J; Spirakis, P; Yung, M

Published Date

  • January 1, 1995

Published In

Volume / Issue

  • 944 /

Start / End Page

  • 160 - 170

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540600841

International Standard Book Number 13 (ISBN-13)

  • 9783540600848

Digital Object Identifier (DOI)

  • 10.1007/3-540-60084-1_71

Citation Source

  • Scopus