Abstrakt. Motiverad av verkliga nätverk och användning av algoritmer baserade på slumpmässiga promenader på dessa nätverk vi studerar de enkla slumpmässiga promenader på dynamiska oriktade grafer med fast underliggande vertex set, dvs. grafer som modifieras genom att infoga eller ta bort kanter vid varje steg av promenaden. Vi är intresserade av den förväntade tid som behövs för att besöka alla hörn av en sådan dynamisk graf, omslagstiden, under antagandet att grafen modifieras av en omedveten motståndare. Det är väl känt att på anslutna statiska oriktade grafer är omslaget tiden polynom i storleken på grafen. Tvärtom och något motintuitivt, visar vi att det finns motståndare strategier som tvingar den förväntade täcka tiden för en enkel slumpmässig promenad på anslutna dynamiska grafer att vara exponentiell. Vi relaterar detta resultat till täckningstiden för statiska riktade grafer. Dessutom ger vi en enkel strategi, den lata slumpmässiga promenaden, som garanterar polynomisk täcktid oavsett de förändringar som görs av motståndaren.
REF:s arbete studerade omslagstiden för slumpmässiga promenader i ett diagram som utvecklades (jfr.
How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
{'venue': 'ICALP', 'journal': None, 'mag_field_of_study': ['Computer Science']}