Jak prohledávat rychle se měnící svět ( Doba pokrytí vyvíjejícího se grafu jednoduchou náhodnou procházkou)

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GP201%2F07%2FP276" target="_blank" >GP201/07/P276: Výpočetní a komunikační složitost Booleovských funkcí a derandomizace</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2008

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of 35th International Colloquium on Automata, Languages and Programming, ICALP 2008

ISBN

978-3-540-70574-1

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

—

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Reykjavik

Datum konání akce

7. 7. 2008

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000258073400011