10 citations · 43 across the 22 of their papers we have counts for
4 papers · 1 filter
Tight tradeoffs for approximating palindromes in streams
Paweł Gawrychowski, Przemysław Uznański
We consider computing the longest palindrome in a text of length in the streaming model, where the characters arrive one-by-one, and we do not have random access to the input.…
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…
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…