How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F08%3A00318518" target="_blank" >RIV/67985840:_____/08:00318518 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
Original language description
Motivated by real world networks and use of algorithms based on random walks on these networks we study the simple random walks on dynamic undirected graphs with fixed underlying vertex set, i.e., graphs which are modifed by inserting or deleting edges at every step of the walk. We are interested in the expected time needed to visit all the vertices of such a dynamic graph, the cover time, under the assumption that the graph is being modified by an oblivious adversary. It is well known that on connectedstatic undirected graphs the cover time is polynomial in the size of the graph. On the contrary and somewhat counter-intuitively, we show that there are adversary strategies which force the expected cover time of a simple random walk on connected dynamic graphs to be exponential.
Czech name
Jak prohledávat rychle se měnící svět ( Doba pokrytí vyvíjejícího se grafu jednoduchou náhodnou procházkou)
Czech description
Studujeme dobu pokrytí vyvíjejících se grafů náhodnými procházkami
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GP201%2F07%2FP276" target="_blank" >GP201/07/P276: Computational and communication complexity of Boolean functions, and derandomization</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of 35th International Colloquium on Automata, Languages and Programming, ICALP 2008
ISBN
978-3-540-70574-1
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
—
Publisher name
Springer
Place of publication
Berlin
Event location
Reykjavik
Event date
Jul 7, 2008
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000258073400011