5 citations · 14 across the 5 of their papers we have counts for
5 papers
Lock-in Problem for Parallel Rotor-router Walks
Jérémie Chalopin, Shantanu Das, Pawel Gawrychowski +3
The rotor-router model, also called the Propp machine, was introduced as a deterministic alternative to the random walk. In this model, a group of identical tokens are initially pl…
Distinguishing Views in Symmetric Networks: A Tight Lower Bound
Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak
The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers , there…
Rendezvous of Distance-aware Mobile Agents in Unknown Graphs
Shantanu Das, Dariusz Dereniowski, Adrian Kosowski +1
We study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However t…
Improved Analysis of Deterministic Load-Balancing Schemes
Petra Berenbrink, Ralf Klasing, Adrian Kosowski +2
We consider the problem of deterministic load balancing of tokens in the discrete model. A set of processors is connected into a -regular undirected network. In every time s…
Faster Walks in Graphs: A Time-Space Trade-off for Undirected s-t Connectivity
Adrian Kosowski
In this paper, we make use of the Metropolis-type walks due to Nonaka et al. (2010) to provide a faster solution to the --connectivity problem in undirected graphs (USTCON).…