Vi presenterar en allmän strategi för att studera översvämningstiden (ett mått på hur snabb information sprids) i dynamiska grafer (grafer vars topologi förändras med tiden enligt en slumpmässig process). Vi anser att godtycklig ergodisk dynamisk grafprocess, dvs. processer där grafens topologi vid tidpunkten t endast beror på dess topologi vid tiden t - 1 och som har en unik stationär fördelning. De mest väl studerade modellerna av dynamiska grafer är alla Markovianska och ergodiska. Under allmänna förhållanden band vi översvämningstiden i termer av blandningstiden för den dynamiska grafprocessen. Vi återhämtar, som speciella fall av vårt resultat, gränser på översvämningstiden för den slumpmässiga resan modellen och den slumpmässiga vägen modeller; tidigare analysmetoder gav gränser endast i begränsade inställningar för sådana modeller. Vårt resultat ger också den första gränsen för den slumpmässiga waypoint modellen (som är tight för de mest realistiska intervallen av nätverksparametrar) vars analys hade varit en viktig öppen fråga.
Nyligen, arbetet med REF, studerar översvämningstiden för Markovianska evolverande dynamiska grafer, en särskild klass av evolverande grafer.
Information spreading in dynamic graphs
{'venue': "PODC '12", 'journal': None, 'mag_field_of_study': ['Computer Science']}