Search results for: DERANDOMIZACJA

• Derandomizing random walks in undirected graphs using locally fair exploration strategies

  Publication

  • C. Cooper
  • D. Ilcinkas
  • R. Klasing
  • A. Kosowski

  - Year 2009

  W pracy rozważono problem eksploracji anonimowego nieskierowanego grafu przez bezpamięciowego robota. Zaprojektowane strategie eksploracji cechują się własnością lokalnej sprawiedliwości, tj. kolejne krawędzie trawersowane przez robota wybierane są na podstawie lokalnych informacji tak, aby zapewnić równomierne wykorzystanie krawędzi w sensie pewnego kryterium. Okazuje się, że odpowiedni dobór kryterium jest kluczowy do zapewnienia...

  Full text to download in external service

• Bounds on the cover time of parallel rotor walks

  Publication

  • D. Dereniowski
  • A. Kosowski
  • D. Pająk
  • P. Uznański

  - JOURNAL OF COMPUTER AND SYSTEM SCIENCES - Year 2016

  The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider...

  Full text available to download